140. Word Break II
改写之前写过的 Word Break I
举例wordDict = aba ba ab a
ababa从结尾拆可以是(ab)aba (aba)ba (abba)a
括号里面可以继续拆
class Solution {
public:
vector<string> wordBreak(string s, vector<string>& wordDict) {
vector<vector<string>> dp(s.size() + 1);
dp[0] = {""};
for(int i = 1; i <= s.size(); i++){
for(auto word : wordDict){
int len = word.size();
if(i - len >= 0 && s.compare(i - len, len, word) == 0){
for(string s : dp[i - len]){
if(s != "")
s += ' ';
dp[i].push_back(s + word);
}
};
}
}
return dp.back();
}
};