Word Break

Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

For example, given
s = "leetcode",
dict = ["leet", "code"].

Return true because "leetcode" can be segmented as "leet code".

思路：

直接使用DFS会超时，增加状态记录，用canForm[j]表示从j到s的末尾是否可以用字典里的词表示，AC。

还可以改成DP的方法。

代码:

 1     int *canForm;
 2     bool wordBreak(string s, int len, unordered_set<string> &dict, int maxlen, int minlen){
 3         if(s.length() < minlen){
 4             return false;
 5         }
 6         if(canForm[len-1] != -1)
 7             return canForm[len-1] == 1;
 8         for(int i = maxlen; i >= minlen; i--){
 9             string tmp = s.substr(0, i);
10             if(dict.find(tmp) == dict.end())
11                 continue;
12             if(tmp == s){
13                 canForm[len-1] = 1;
14                 return true;
15             }
16             if(wordBreak(s.substr(i), len-i, dict, maxlen, minlen)){
17                 canForm[len-1] = 1;
18                 return true;
19             }
20         }
21         canForm[len-1] = 0;
22         return false;
23     }
24     bool wordBreak(string s, unordered_set<string> &dict) {
25         // IMPORTANT: Please reset any member data you declared, as
26         // the same Solution instance will be reused for each test case.
27         if(s == "")
28             return true;
29         int maxlen = 0;
30         int minlen = INT_MAX;
31         canForm = new int[s.length()];
32         memset(canForm, -1, sizeof(int)*s.length());
33         for(unordered_set<string>::iterator it = dict.begin(); it != dict.end(); it++){
34             if(maxlen < (*it).length())
35                 maxlen = (*it).length();
36             if(minlen > (*it).length())
37                 minlen = (*it).length();
38         }
39         int l = s.length();
40         return wordBreak(s, l, dict, maxlen, minlen);
41     }

DFS第二遍：

 1     bool search(string s, int index, int canBreak[],  unordered_set<string> &dict){
 2         if(canBreak[index] != -1)
 3             return canBreak[index] == 1;
 4         for(int i = index; i < s.length(); i++){
 5             string tmp = s.substr(index, i-index+1);
 6             if(dict.find(tmp) != dict.end()){
 7                 if(search(s, i+1, canBreak, dict)){
 8                     canBreak[index] = 1;
 9                     return true;
10                 }
11             }
12         }
13         canBreak[index] = 0;
14         return false;
15     }
16     bool wordBreak(string s, unordered_set<string> &dict) {
17         // IMPORTANT: Please reset any member data you declared, as
18         // the same Solution instance will be reused for each test case.
19         int l = s.length();
20         if(l == 0)
21             return true;
22         int canBreak[l+1];
23         memset(canBreak, -1, sizeof(canBreak));
24         canBreak[l] = 1;
25         return search(s, 0, canBreak, dict);
26     }

DP的解法：

 1     bool wordBreak(string s, unordered_set<string> &dict) {
 2         // IMPORTANT: Please reset any member data you declared, as
 3         // the same Solution instance will be reused for each test case.
 4         int l = s.length();
 5         bool canBreak[l+1];
 6         memset(canBreak, false, sizeof(canBreak));
 7         canBreak[0] = true;
 8         int i,j;
 9         for(i = 1; i <= l; i++){
10             if(canBreak[i-1]){
11                 for(j = i-1; j < l; j++){
12                     string tmp = s.substr(i-1, j-i+2);
13                     if(dict.find(tmp) != dict.end())
14                         canBreak[j+1] = true;
15                 }
16             }
17         }
18         return canBreak[l];
19     }