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"].
C++
class Solution { public: vector<string> wordBreak(string s, unordered_set<string> &dict){ vector<string> result; if(dict.find(s)!=dict.end()) result.push_back(s); for(int i=1;i<s.size();i++) { string w = s.substr(i); if(dict.find(w) == dict.end()) continue; string str = s.substr(0,i); vector<string> left = wordBreak(str,dict); Add(left,w); result.insert(result.begin(), left.begin(), left.end()); } return result; } void Add(vector<string> &str, string w){ for(vector<string>::iterator it=str.begin();it!=str.end();it++) *it += " " + w; } vector<string> wordBreak2(string s, unordered_set<string> &dict){ vector<string> result; if (dict.find(s) != dict.end()) result.push_back(s); for(int i = s.size() -1; i > 0;i--){ string w = s.substr(i); if(dict.find(w) == dict.end()) continue; string str = s.substr(0,i); vector<string> left = wordBreak(str,dict); Add(left,w); result.insert(result.end(),left.begin(),left.end()); } return result; } };
转载于:https://www.cnblogs.com/vercont/p/10210240.html
