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"].
这题没有AC，但是做出了递归回朔的版本，最后一个一串a后面跟个b的case超时了没法通过。
sand -- [dog] ->"cat sand dog"
/
cat --[sanddog]
/
[catsanddog]
\
cats --[anddog]
\
and -- [dog] -> "cats and dog"
从这个结构可以看出，这个问题可以被分解为当前的问题＋更小规模的同类子问题，用递归求解。
我用了一个vector<stirng>来记录每个阶段（路径）上的结果，当搜索完字符串的时候(left >= right)意味着数组里的就是一个结果。
void wb(string s, int left, int right, unordered_set<string> &dict, vector<string> t, vector<string> &re) {
if (s.length() <= )
return;
if (left >= right) {
string k;
for (int i=; i<t.size(); i++) {
if (i != t.size()-) {
k = k + t[i] + " ";
}
else
k+=t[i];
}
re.push_back(k);
return;
}
//find matches
for (const auto& elem: dict) {
int len = (int)((string)elem).size();
if (left+len > s.length()) continue;
string sub = s.substr(left, len);
if (elem.compare(sub) == ) {
t.push_back(sub);
wb(s, left+len, right, dict, t, re);
if (t.size())
t.pop_back();
}
}
}
vector<string> wordBreak(string s, unordered_set<string> &dict) {
vector<string> ret;
vector<string> t;
wb(s, , s.size()-, dict,t, ret);
return ret;
}
在编写过程中遇到的两个bug都是因为没有很好理解程序造成的，第一个是t数组，一开始我传起引用，结果发现最后结果集翻倍。。。 第二个是调用wb后 t 没有pop，这样就把前一个分支的内容带到了下一分支造成错乱。
求大神指导如何AC