Given a string s and a dictionary of words dict, add spaces in s 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"].
和上一题一样，如果直接在dp的过程中记录路径，会MLE，因为存储了许多不必要的中间结果。
在一开始MLE的基础上，我做了一点优化，与之前单词梯的方法类似，先记录前驱节点，这样比直接记大量字符串节省空间，最后dfs跑一边结果。
代码语言：javascript复制class Solution {
public:
void dfs(vector<string> &res, string now, vector<vector<int>>& dp, int index, string& s)
{
if (index == 0)
{
now = now.substr(0, now.size()-1);
res.push_back(now);
return ;
}
for(int i = 0; i < dp[index].size(); i )
{
dfs(res, s.substr(dp[index][i], index - dp[index][i]) " " now, dp, dp[index][i], s);
}
}
vector<string> wordBreak(string s, unordered_set<string>& wordDict) {
vector<int> temp;
vector<vector<int>> dp(s.size() 1, temp);
dp[0].push_back(0);
for (int i = 1; i<= s.size(); i )
{
for(int j = 0; j < i; j )
{
if(dp[j].empty()) continue;
if(wordDict.find(s.substr(j, i-j)) != wordDict.end()) dp[i].push_back(j);
}
}
vector<string> res;
string now;
dfs(res, now, dp, s.size(), s);
return res;
}
};
