class Solution
{
public:
bool wordBreak(std::string s, std::vector<std::string> &wordDict){
std::vector<bool> dp(s.size() + 1, false);
dp[0] = true;
for (int j = 0; j < s.size() + 1; j++)
for (int i = 0; i < j; i++){
std::string word = s.substr(i, j - i);
if (dp[i] == true && (std::find(wordDict.begin(), wordDict.end(), word)) != wordDict.end())
dp[j] = true;
}
return dp[s.size()];
}
};
class Solution {
public:
bool wordBreak(std::string s, std::vector<std::string>& wordDict) {
// 错写成 unordered_set<string> wordset = (wordDict.begin(), wordDict.end());
std::unordered_set<std::string> wordset(wordDict.begin(), wordDict.end());
// dp[j] 字符串s长度 是true or false
std::vector<bool> dp(s.size()+1, false);
dp[0] = true;
// dp[j] 多增加一项dp[0] 长度s.size()+1 保证i<j j从1开始
for (int j=1;j<s.size()+1;j++)// 先背包 求的是排列数
// 本题的物品不是wordDict里元素，物品是word-s的子串，在wordDict里找word
for (int i=0;i<j;i++){
std::string word = s.substr(i, j-i);
if (dp[i] && wordset.find(word)!=wordset.end()) dp[j] = true;
}
return dp[s.size()];
}
};