139. Word Break
C++，动态规划。dfs也是可以的，但是一定得存储之前搜索的结果，本质还是动态规划。
其实就是三个步骤：
- 在字符串s中从前往后找到第一个单词，记录下这个单词已经完整找到了，反应在代码中就是
dp[i] = true； - 继续找第二个单词，找到第二个单词并且确定之前已经有完整的单词；
- 重复上述过程，直到从头到尾找出s中所有单词。
- 返回
true还是false取决于是不是所有的单词都是完整的，也是最后dp[s.size() - 1]的值。
Tips：
- 可以用
string类的substr()方法取子串； unordered_set直接find查找不仅比unodered_map映射表hash快，而且省内存。。。
代码如下：
class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
int m = s.size();
vector<bool> dp(m, false);
unordered_set<string> set_s(wordDict.begin(), wordDict.end());
int i = 0;
for (; i < m; i++) {
string it = s.substr(0, i + 1);
if (set_s.find(it) != set_s.end()) break;
}
for (; i < m; i++) {
for (int j = i; j >= 0; j--) {
string it = s.substr(j, i - j + 1);
if (set_s.find(it) != set_s.end()) {
if (j == 0 || dp[j-1]) {
dp[i] = true;
break;
}
}
}
}
return dp[m-1];
}
};
