**LeetCode—Word Break

http://blog.csdn.net/xietingcandice/article/details/43705383

Given a string s and a dictionary of words dict, determine ifs 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".

在这个例子当中，主要是为了看一个句子字符串中的词语能不能够都划分为词典中的词语

flag[j]为true，那么就是要求存在一个变量k,能够满足flag[k]为ture,同时substr(k,j-k)是在字典当中的

但是在这个例子当中是不关心最终的划分方式

[cpp] view plaincopyprint?

1. class Solution {    
2. public:    
3. bool wordBreak(string s, unordered_set<string> &dict) {    
4. int length = s.size();  
5. vector<bool> val(length+1,false);  
6. val[0] = true; //<根据长度进行设置
7. int i = 0;  
8. int j = 0;  
9. for(i = 0; i < length; i++)  
10. {  
11. if(val[i])//<前一个长度是可以进行分解的
12.     {  
13. for(j = 1; (i+j) <= length; j++)  
14.         {  
15.             string tmp = s.substr(i,j);  
16. if(dict.count(tmp) > 0)  
17.             {  
18.                 val[i+j] = true;  
19.             }  
20.         }  
21.     }  
22. }  
23. return val[length];  
24.        }    
25.    };    

对应着有第二个例子：

Word Break II

Given a string s and a dictionary of words dict, add spaces ins 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"].

在这个例子当中，主要是需要将分解的结果放在一个vector的结构体当中

有一种方法是DFS 方法，还没有研究

这里主要还是借鉴了第一个例子当中的方法，先检测是否能够被划分，如果可以被划分，之后再通过遍历进行存储

[cpp] view plaincopyprint?

1. class Solution {  
2. public:  
3. void breakWord(vector<string> &res, string &s, unordered_set<string> &dict, string str, int idx, vector<bool> &dp) {  
4.         string substr;  
5. for (int len = 1; idx + len <= s.length(); ++len) {  
6. if (dp[idx + len] && dict.count(s.substr(idx,len)) > 0) {  
7.                 substr = s.substr(idx, len);  
8. if (idx + len < s.length()) {  
9.                     breakWord(res, s, dict, str + substr + " ", idx + len, dp);  
10.                 } else {  
11.                     res.push_back(str + substr);  
12. return;  
13.                 }  
14.             }  
15.         }  
16.     }  
18.     vector<string> wordBreak(string s, unordered_set<string> &dict) {  
19.         vector<bool> dp(s.length() + 1, false);  
20.         dp[0] = true;  
21. for (int i = 0; i < s.length(); ++i) {  
22. if (dp[i]) {  
23. for (int len = 1; i + len <= s.length(); ++len) {  
24. if (dict.count(s.substr(i, len)) > 0) {  
25.                         dp[i + len] = true;  
26.                     }  
27.                 }  
28.             }  
29.         }  
30.         vector<string> res;  
31. if (dp[s.length()])   
32.             breakWord(res, s, dict, "", 0, dp);  
33. return res;  
34.     }  
35. };