140. Word Break II

My intuition is to use backtracking solution directly. But it get TLE. So we definitely need to do some memorization.

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:  };