Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.
For example, given
s = "leetcode",
dict = ["leet", "code"].
Return true because "leetcode" can
be segmented as "leet code".
思路：刚开始用递归，在一些特殊测试用例中超时，以下是超时代码：
class Solution {
private:
bool res;
public:
void DFS(string &s, vector<vector<string> > &f, int pos) {
if (pos == s.length()) {
res = true;
return;
}
if (res) {
return;
}
int i;
for(i=0; i<s.size(); ++i) {
if (pos+i<s.size() && f[pos][pos+i] != "\0") {
DFS(s,f,pos+i+1);
}
}
}
bool wordBreak(string s, unordered_set<string> &dict) {
if (dict.empty()) {
return false;
}
vector<vector<string> > f(s.size(),vector<string>(s.size(),"\0"));
int i,j,n=s.length();
string str;
for(i=0; i<n; ++i) {
str = "";
for(j=i; j<n; ++j) {
str += s[j];
if (dict.find(str) != dict.end()) {
f[i][j] = str;
}
}
}
res = false;
DFS(s,f,0);
return res;
}
};
后来参考别人的解题报告，在给位置i的后缀未匹配时做保存，即可满足时间复杂度要求。
class Solution {
private:
int maxLen;
int minLen;
bool res;
public:
bool DFS(string s, unordered_set<string> &dict, unordered_set<string> &unMathced) {
if (s.size() < 1) {
return true;
}
int i;
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;
}
if (DFS(suffix,dict,unMathced)) {
return true;
}
else {
unMathced.insert(suffix);
}
}
return false;
}
bool wordBreak(string s, unordered_set<string> &dict) {
if (dict.empty()) {
return false;
}
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;
res = false;
return DFS(s,dict,unMatched);
}
};