【题目】
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"].
【题意】
给定一个字符串s和词典dict, 返回全部切分情况。使得切分后每一个单词都是dict中的单词【思路】
依次确定以每一个位置i结尾的单词的前驱单词集合（仅仅要记住前驱单词的结束位置）然后从后往前恢复切分路径就可以。
DP问题
【代码】
class Solution {
public:
void recoverPath(vector<string>&result, vector<string>&words, string&s, map<int, vector<int> >preorders, int end){
vector<int>preorder=preorders[end];
for(int i=0; i<preorder.size(); i++){
string word=s.substr(preorder[i]+1, end-preorder[i]);
if(preorder[i]==-1){
string cutstr=word;
int size=words.size();
for(int j=size-1; j>=0; j--){
cutstr+=" "+words[j];
}
result.push_back(cutstr);
}
else{
words.push_back(word);
recoverPath(result, words, s, preorders, preorder[i]);
words.pop_back();
}
}
}
vector<string> wordBreak(string s, unordered_set<string> &dict) {
vector<string> result;
if(s.length()==0)return result;
map<int, vector<int> >preorders; //记录各个可分位置的前驱集合
vector<int> pos(1,-1); //以确定可分的位置
for(int i=0; i<s.length(); i++){
vector<int>preorder;
for(int k=0; k<pos.size(); k++){
if(dict.find(s.substr(pos[k]+1, i-pos[k]))!=dict.end()){
preorder.push_back(pos[k]);
}
}
if(preorder.size()>0){
preorders[i]=preorder;
pos.push_back(i);
}
}
//恢复全部可能的切分路径
if(preorders.find(s.length()-1)==preorders.end())return result;
vector<string>words;
recoverPath(result, words, s, preorders, s.length()-1);
return result;
}
};
本文转自mfrbuaa博客园博客，原文链接：http://www.cnblogs.com/mfrbuaa/p/5354673.html，如需转载请自行联系原作者
