# **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)是在字典当中的

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"]`.

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.     }
17.     vector<string> wordBreak(string s, unordered_set<string> &dict) {
18.         vector<bool> dp(s.length() + 1, false);
19.         dp[0] = true;
20. for (int i = 0; i < s.length(); ++i) {
21. if (dp[i]) {
22. for (int len = 1; i + len <= s.length(); ++len) {
23. if (dict.count(s.substr(i, len)) > 0) {
24.                         dp[i + len] = true;
25.                     }
26.                 }
27.             }
28.         }
29.         vector<string> res;
30. if (dp[s.length()])
31.             breakWord(res, s, dict, "", 0, dp);
32. return res;
33.     }
34. };

851 篇文章41 人订阅

0 条评论

## 相关文章

82540

13540

13810

18640

3.1K30

18790

30840

### 什么样的人生才是有意义的人生——没有标准的标准答案

【导读】其实我们可以跳出这个小圈圈去更加科客观地看一下这个世界。在夜晚的时候我们仰望天空，浩瀚的宇宙中整个地球只是一粒浮尘，何况地球上一个小小的人类？在漫长的历...

1.7K50

21770

### 儿童编程Scratch之“画笔”基础功能学习总结

Scratch中“画笔”功能能够让使用者模拟画笔在舞台上创作，合理运用能够给作品带来极大的趣味性。

65020