The typical solution to this problem is to use Dynamic Programming. The state dp[i] represents whether s[0..i - 1] can be broken into words in wordDict and the state equation is:
dp[i] = true, if there exists j < i such that dp[j] = true and s.substr(j, i - j) is in wordDict
dp[i] = false, otherwise.
The code is as follows (we use minlen and maxlen to reduce the number of checks).
1 class Solution { 2 public: 3 bool wordBreak(string s, unordered_set<string>& wordDict) { 4 int n = s.length(); 5 vector<bool> dp(n + 1, false); 6 dp[0] = true; 7 for (string word : wordDict) { 8 minlen = min(minlen, (int)word.length()); 9 maxlen = max(maxlen, (int)word.length()); 10 } 11 for (int i = 1; i <= n; i++) { 12 for (int j = i - minlen; j >= max(0, j - maxlen); j--) { 13 if (dp[j] && wordDict.find(s.substr(j, i - j)) != wordDict.end()) { 14 dp[i] = true; 15 break; 16 } 17 } 18 } 19 return dp[n]; 20 } 21 private: 22 int minlen, maxlen; 23 };
This problem can also be solved using DFS or BFS.
DFS:
1 class Solution { 2 public: 3 bool wordBreak(string s, unordered_set<string>& wordDict) { 4 for (string word : wordDict) { 5 minlen = min(minlen, (int)word.length()); 6 maxlen = max(maxlen, (int)word.length()); 7 } 8 unordered_map<string, bool> records; 9 return wordBreakDFS(s, 0, wordDict, records); 10 } 11 private: 12 int minlen, maxlen; 13 bool wordBreakDFS(string& s, int idx, unordered_set<string>& wordDict, unordered_map<string, bool>& records) { 14 int n = s.length(); 15 if (idx == n) return true; 16 string tail = s.substr(idx, n - idx); 17 if (records.find(tail) != records.end()) 18 return records[tail]; 19 for (int i = idx + minlen; i <= min(idx + maxlen, n); i++) { 20 string part = s.substr(idx, i - idx); 21 if (wordDict.find(part) != wordDict.end() && wordBreakDFS(s, i, wordDict, records)) 22 return records[part] = true; 23 } 24 return records[tail] = false; 25 } 26 };
BFS:
1 class Solution { 2 public: 3 bool wordBreak(string s, unordered_set<string>& wordDict) { 4 int n = s.length(); 5 for (string word : wordDict) { 6 minlen = min(minlen, (int)word.length()); 7 maxlen = max(maxlen, (int)word.length()); 8 } 9 queue<int> toVisit; 10 unordered_set<int> visited; 11 toVisit.push(0); 12 while (!toVisit.empty()) { 13 int start = toVisit.front(); 14 toVisit.pop(); 15 if (visited.find(start) == visited.end()) { 16 visited.insert(start); 17 for (int end = start + minlen - 1; end < min(start + maxlen, n); end++) { 18 string part = s.substr(start, end - start + 1); 19 if (wordDict.find(part) != wordDict.end()) { 20 if (end + 1 == n) return true; 21 toVisit.push(end + 1); 22 } 23 } 24 } 25 } 26 return false; 27 } 28 private: 29 int minlen, maxlen; 30 };
