DP+
剪枝
class Solution {
public:
bool dfs(
string s, unordered_set<
string> &dict, unordered_set<
string> &unmatch,
int maxLen, vector<
string> &result,
string path){
if (s.size() ==
0){
path.pop_back();
result.push_back(path);
return true;
}
bool flag =
false;
int size =
s.size();
for (
int i =
1; i <= min(maxLen,size); i++
){
if (dict.find(s.substr(
0,i)) !=
dict.end()){
if (unmatch.find(s.substr(i) )==
unmatch.end()){
path+=s.substr(
0,i);
path.push_back(' ');
if (dfs(s.substr(i), dict, unmatch, maxLen, result, path)) flag =
true;
else unmatch.insert(s.substr(i));
for (
int j =
0; j < i+
1; j++
) path.pop_back();
}
}
}
return flag;
}
vector<
string> wordBreak(
string s, unordered_set<
string> &
dict) {
// Note: The Solution object is instantiated only once and is reused by each test case.
vector<
string>
result;
if (s.size() ==
0)
return result;
int maxLen =
0;
unordered_set<
string>
:: iterator it;
for (it = dict.begin(); it != dict.end(); it++
){
if (it->size() > maxLen) maxLen = it->
size();
}
unordered_set<
string>
unmatch;
string path;
bool hasAnswer =
dfs(s,dict,unmatch,maxLen,result,path);
return result;
}
};
转载于:https://www.cnblogs.com/tanghulu321/p/3390472.html
