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"].
DFS+剪枝
是前面那拆分词语的扩展，除了要判断能否由字典里的词语组成，还要求出所有的组合。
单纯的DFS会TLE，需要剪枝。
class Solution{
private:
void helper(string& s,unordered_set<string>& wordDict,int start,vector<bool>& possible,string path,vector<string>& res){
if(start == int(s.length())){
res.push_back(path);
return;
}
for(int i = start;i<int(s.length());i++){
string word = s.substr(start,i-start+);
if(wordDict.find(word) != wordDict.end() && possible[i+]){
if(start == )
path.append(word);
else{
path.append(" ");
path.append(word);
}
int oldsize = res.size();
helper(s,wordDict,i+,possible,path,res);
if(int(res.size()) == oldsize) possible[i+] = false;
if(start == )
path.resize(path.size() - word.size());
else
path.resize(path.size() - word.size()-);
}
}
}
public:
vector<string> wordBreak(string s,unordered_set<string>& wordDict){
vector<string> res;
vector<bool> possible(s.size()+,true);
helper(s,wordDict,,possible,"",res);
return res;
}
};