1: class Solution {
2: public:
3: vector<string> wordBreak(string s, unordered_set<string>& wordDict) {
4: vector<string> res;
5: helper(s, 0, wordDict, "", res);
6: return res;
7: }
8: void helper(string s, int i, unordered_set<string> &wordDict, string sol, vector<string> &res) {
9: if (i == s.size()) { sol.pop_back(); res.push_back(sol); return;}
10: for (int j = i; j < s.size(); j++) {
11: string word = s.substr(i, j-i+1);
12: if (wordDict.count(word) == 0) continue;
13: helper(s, j+1, wordDict, sol+word+" ", res);
14: }
15: }
16: };
Let’s look at one example first. Say, we have string “aaaab”, dictionary [“a”, “aa”]. Then let’s see how the solution above works.
Step 1: “a a a a” and “b” not valid.
Setp 2: “a a a” and recursively check “ab”.
Step 3: “a a aa” and “b” not valid.
Step 4: “a a” and recursively check “aab”.
Step 5: “a aa” and recursively check “ab”.
Step 6: “aa” and recursively check “aab”.
From here, we can see in Step 5 we don’t have to recursively check “ab” again because from Step 2 we already know that “ab” is not breakable. Same to Step 6. So if we can memorize if word[i..n-1] is breakable, then we can speed up the solution. Let dp[i] be that s[i..n-1] is not breakable. And then the trick becomes how to update the dp[i]. If there is no breakable words, no new solution will be added to the result. So we can update the dp[i] upon that.
1: class Solution {
2: private:
3: vector<bool> dp;
4: public:
5: vector<string> wordBreak(string s, unordered_set<string>& wordDict) {
6: vector<string> res;
7: dp = vector<bool>(s.size(), true);
8: helper(s, 0, wordDict, "", res);
9: return res;
10: }
11: void helper(string s, int i, unordered_set<string> &wordDict, string sol, vector<string> &res) {
12: if (i == s.size()) { sol.pop_back(); res.push_back(sol); return;}
13: for (int j = i; j < s.size(); j++) {
14: string word = s.substr(i, j-i+1);
15: int res_sz = res.size();
16: if (wordDict.count(word) == 0 || !dp[j]) continue;
17: helper(s, j+1, wordDict, sol+word+" ", res);
18: if (res_sz == res.size()) dp[j] = false;
19: }
20: }
21: };
No comments:
Post a Comment