139. Word Break

My intuition is simple DFS.

1:  class Solution {  
2:  public:  
3:    bool wordBreak(string s, unordered_set<string>& wordDict) {  
4:      if (s.size() == 0) return true;  
5:      for (int i = 1; i <= s.size(); i++) {  
6:        if (wordDict.count(s.substr(0, i)) != 0 && wordBreak(s.substr(i), wordDict)) return true;  
7:      }  
8:      return false;  
9:    }  
10:  };  

However, this simple solution gets TLE. Why TLE? Let's look at an easy example,
"aaab", ["a", "aa", "aaa"]
1st round loop, we'll find "a" to be true until "b".
2nd round, we'll check if "aa" is in dictionary. Though it's in dictionary, we already know that "aa" can be word break into two "a". If we can memorize the word break result from 1st round loop, we don't have to check the dictionary which save a lot cost. So we can do it by memorization.

1:  class Solution {  
2:  public:  
3:    bool wordBreak(string s, unordered_set<string>& wordDict) {  
4:      vector<bool> dp(s.size(), false);  
5:      helper(s, wordDict, dp, 0);  
6:      return dp[s.size()-1];  
7:    }  
8:    void helper(string s, unordered_set<string> &wordDict, vector<bool> &dp, int start) {  
9:      if (start == s.size() || dp[start]) return;  
10:      for (int i = start; i < s.size(); i++) {  
11:        string ss = s.substr(start, i-start+1);  
12:        if (wordDict.count(s.substr(start, i-start+1)) != 0) {  
13:          dp[i] = true;  
14:          helper(s, wordDict, dp, i+1);  
15:        }  
16:      }  
17:    }  
18:  };  

Of course, inspired by memorization, it can be solved by DP. Let dp[i] be that there is valid word break sequence ending at position i.

1:  class Solution {  
2:  public:  
3:    bool wordBreak(string s, unordered_set<string>& wordDict) {  
4:      vector<bool> dp(s.size()+1, false);  
5:      dp[0] = true;  
6:      for (int i = 1; i <= s.size(); i++) {  
7:        for (int j = i-1; j >= 0; j--) {  
8:          if (dp[j]) {  
9:            if (wordDict.count(s.substr(j, i-j)) != 0) {  
10:              dp[i] = true;  
11:              break;  
12:            }  
13:          }  
14:        }  
15:      }  
16:      return dp[s.size()];  
17:    }  
18:  };