1. Introduction
This blog post focuses on solving the "Word Break" problem in C++, a classic problem often encountered in coding interviews. The problem involves checking whether a given string can be segmented into a sequence of dictionary words.
Problem
Given a string s and a dictionary of strings wordDict, we need to determine whether s can be segmented into a space-separated sequence of one or more dictionary words.
2. Solution Steps
1. Use dynamic programming to solve this problem.
2. Create a boolean array dp where dp[i] indicates whether the substring s[0..i-1] can be segmented into dictionary words.
3. Initialize dp[0] to true.
4. For each position in the string, check if the substring ending at that position can be segmented into words in the dictionary.
5. If a valid segmentation is found, set dp[i] to true.
6. Return the value of dp[s.length()].
3. Code Program
#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;
// Function to check if the string can be segmented into words from the dictionary
bool wordBreak(string s, vector<string>& wordDict) {
unordered_set<string> dict(wordDict.begin(), wordDict.end());
vector<bool> dp(s.length() + 1, false);
dp[0] = true;
for (int i = 1; i <= s.length(); i++) {
for (int j = 0; j < i; j++) {
if (dp[j] && dict.find(s.substr(j, i - j)) != dict.end()) {
dp[i] = true;
break;
}
}
}
return dp[s.length()];
}
int main() {
vector<string> wordDict = {"leet", "code"};
string s = "leetcode";
cout << "Can segment: " << wordBreak(s, wordDict) << endl;
return 0;
}
Output:
Can segment: 1
Explanation:
1. The input string "leetcode" is processed to check if it can be segmented into words from the dictionary ["leet", "code"].
2. The dynamic programming approach checks each substring and verifies if it can form a word in the dictionary.
3. The substring "leet" is found in the dictionary, setting dp[4] to true.
4. The process continues, and "code" is also found, leading to dp[8] being true.
5. The function returns true (represented as 1), indicating that the string can indeed be segmented into words from the dictionary.
Comments
Post a Comment