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"]
思路：在I的基础上保存各个可能性的结果。
class Solution {
private:
int maxLen;
int minLen;
bool res;
vector<string> result;
public:
string generate(vector<string> &saved) {
int i,len=saved.size();
string str = "";
for(i=0; i<len; ++i) {
str += saved[i];
if (i!=len-1)
str += " ";
}
return str;
}
bool DFS(string s, unordered_set<string> &dict, unordered_set<string> &unMathced, vector<string> &saved, int pos) {
if (s.size() < 1) {
result.push_back(generate(saved));
return true;
}
int i;
bool flag = false;
for(i=minLen; i<=maxLen&&i<=s.size(); ++i) {
string preSuffix = s.substr(0, i);
if (dict.find(preSuffix) == dict.end()) {
continue;
}
string suffix = s.substr(i);
if (unMathced.find(suffix) != unMathced.end()) {
continue;
}
saved.resize(pos+1);
saved[pos] = preSuffix;
if (DFS(suffix,dict,unMathced, saved, pos+1)) {
flag = true;
}
else {
unMathced.insert(suffix);
}
}
return flag;
}
vector<string> wordBreak(string s, unordered_set<string> &dict) {
result.clear();
if (dict.empty()) {
return result;
}
unordered_set<string>::iterator it;
maxLen = 0;
minLen = INT_MAX;
for(it=dict.begin(); it!=dict.end(); ++it) {
if (maxLen < (*it).size()) {
maxLen = (*it).size();
}
if (minLen > (*it).size()) {
minLen = (*it).size();
}
}
unordered_set<string> unMatched;
vector<string> saved;
res = false;
DFS(s,dict,unMatched,saved,0);
return result;
}
};