139. Word Break
字符串能否通过划分成词典中的一个或多个单词。
使用动态规划，dp[i]表示当前以第i个位置(在字符串中实际上是i-1)结尾的字符串能否划分成词典中的单词。
j表示的是以当前i的位置往前找j个单词，如果在j个之前能正确分割，那只需判断当前这j单词能不能在词典中找到单词。j的个数不能超过词典最长单词的长度，且同时不能超过i的索引。
初始化时要初始化dp[0]为true，因为如果你找第一个刚好匹配成功的，你的dp[i - j]肯定就是dp[0]。因为多申请了一个，所以dp中的i相当于s中的i-1。
s.substr(i-j,j)实际上是s.substr(i-j + 1 - 1,j)，因为本身应该提取i - j +1，但因为dp位置比s多一个，所以还要-1。
class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
int length = ;
for(string word : wordDict){
if(word.size() > length)
length = word.size();
}
vector<bool> dp(s.size() + ,false);
dp[] = true;
for(int i = ;i <= s.size();i++){
for(int j = ;j <= length && j <= i;j++){
if(dp[i-j]){
string str = s.substr(i-j,j);
for(string word : wordDict){
if(word == str){
dp[i] = true;
break;
}
}
}
}
}
return dp[s.size()];
}
};140. Word Break II
一个字符串加空字符串还是原字符串
class Solution {
public:
vector<string> wordBreak(string s, vector<string>& wordDict) {
unordered_map<string, vector<string>> m;
return helper(s, wordDict, m);
}
vector<string> helper(string s, vector<string>& wordDict, unordered_map<string, vector<string>>& m) {
if (m.count(s)) return m[s];
if (s == "") return {""};
vector<string> res;
for (string word : wordDict) {
if (s.substr(, word.size()) != word) continue;
vector<string> rem = helper(s.substr(word.size()), wordDict, m);
for (string str : rem) {
res.push_back(word + (str.empty() ? "" : " ") + str);
}
}
m[s] = res;
return res;
}
};