Word Break
Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words.
Constraints:
- 1 <= s.length <= 300
- 1 <= wordDict.length <= 5000
- 1 <= wordDict[i].length <= 20
- s and wordDict[i] consist of lowercase English letters.
- 0 <= i <= wordDict.length - 1
Examples:
Input: s = "leetcode", wordDict = ["leet","code"]
Output: true
Explanation: "leetcode" can be segmented into "leet" and "code".
Input: s = "applepenapple", wordDict = ["apple","pen"]
Output: true
Explanation: "applepenapple" can be segmented into "apple", "pen", and "apple".
Input: s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]
Output: false
Explanation: There is no way to segment "catsandog" into words in the dictionary.
Solutions
Dynamic Programming
The dynamic programming approach involves creating a boolean array dp where dp[i] is true if the substring s[0..i] can be segmented into words in the dictionary. We initialize dp[0] to true and then iterate over the string, checking for each substring if it can be segmented by checking all substrings ending at the current position.
class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
vector<bool> dp(s.size() + 1, false);
dp[0] = true;
for (int i = 1;
i <= s.size();
i++) {
for (int j = 0;
j < i;
j++) {
if (dp[j] && find(wordDict.begin(), wordDict.end(), s.substr(j, i - j)) {
dp[i] = true;
break;
}
}
}
return dp.back();
}
}
;Follow-up:
How would you optimize the solution if the dictionary is very large?
