Word Break II

Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word.

Return all such possible sentences.

For example, given
s = "catsanddog",
dict = ["cat", "cats", "and", "sand", "dog"].

A solution is ["cats and dog", "cat sand dog"].

思路：

思路类似于Word Break，不过在那题的基础上增加了一个vector<vector<string> > result, 用来记录从 i 出发的字符串可能表示的种类。

代码：

 1     vector<vector<string> > result;
 2     vector<int> canForm;
 3     void wordBreak(string s, unordered_set<string> &dict, int start, int min, int max){
 4         if(canForm[start] != -1){
 5             return;
 6         }
 7         int len = s.length();
 8         if(len < start+min){
 9             canForm[start] = 0;
10             return;
11         }
12         int i, j;
13         for(i = min; i <= max; i++){
14             if(start + i == len){
15                 break;
16             }
17             string tmp = s.substr(start, i);
18             if(dict.find(tmp) != dict.end()){
19                 if(canForm[start+i] == -1)
20                     wordBreak(s, dict, start+i, min, max);
21                 if(canForm[start+i] == 1){
22                     canForm[start] = 1;
23                     for(j = 0; j < result[start+i].size(); j++){
24                         result[start].push_back(tmp+" "+result[start+i][j]);
25                     }
26                 }
27             }
28         }
29         if(start + i == len){
30             string tmp = s.substr(start);
31             if(dict.find(tmp) != dict.end()){
32                 canForm[start] = 1;
33                 result[start].push_back(tmp);
34             }
35         }
36         if(canForm[start] == -1)
37             canForm[start] = 0;
38     }
39     vector<string> wordBreak(string s, unordered_set<string> &dict) {
40         // IMPORTANT: Please reset any member data you declared, as
41         // the same Solution instance will be reused for each test case.
42         int len = s.length();
43         result = vector<vector<string> >(len);
44         canForm = vector<int>(len, -1);
45         int max = INT_MIN;
46         int min = INT_MAX;
47         for(unordered_set<string>::iterator i = dict.begin(); i != dict.end() ; i++){
48             int length = i->length();
49             max = max > length ? max : length;
50             min = min < length ? min : length;
51         }
52         if(len < min)
53             return result[0];
54         wordBreak(s, dict, 0, min, max);
55         return result[0];
56     }

第二遍深搜：

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