Word Break
LeetCode #139 · Medium · Dynamic Programming · C++ solution with worked-out approach and complexity analysis.
Approach
Dynamic Programming
Key insight
If we can break s[0..j-1] into valid words, and s[j..i-1] is also a valid word, then we can break s[0..i-1] into valid words.
Time
O(n^2 * m)
n = s.length, m = avg word length
Space
O(n + k)
k = total chars in wordDict
Problem description(from LeetCode)
Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words. Note that the same word in the dictionary may be reused multiple times.
Examples
Example 1
- Input:
- s = "leetcode", wordDict = ["leet","code"]
- Output:
- true
- Note:
- Return true because "leetcode" can be segmented as "leet code". Input: s = "applepenapple", wordDict = ["apple","pen"] Output: true Input: s = "catsandog", wordDict = ["cats","dog","sand","and","cat"] Output: false
Constraints
- •1 <= s.length <= 300
- •1 <= wordDict.length <= 1000
- •1 <= wordDict[i].length <= 20
- •s and wordDict[i] consist of only lowercase English letters.
- •All the strings of wordDict are unique.
C++ Solution
solution.cpp
class Solution {
public:
bool wordBreak(string s, vector<string> &wordDict) {
unordered_set<string> dict(wordDict.begin(), wordDict.end());
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] && dict.count(s.substr(j, i - j))) {
dp[i] = true;
break;
}
}
}
return dp[s.size()];
}
};