田同学
暴力DFS超时，时间复杂度指数量级
class Solution {
public:
bool flag;
bool wordBreak(string s, vector<string>& wordDict) {
dfs(s,0,wordDict);
return flag;
}
void dfs(string s, int start, vector<string>& wordDict){
int n = s.size();
if(start==n) flag=true;
for(int i=0;i<wordDict.size();i++){
int m = wordDict[i].size();
if(start+m<=s.size()&&s.substr(start,m)==wordDict[i]){A
dfs(s,start+m, wordDict);
}
}
}
};
动态规化优化：
class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
int n= s.size();
vector<bool> dp(n+1,false);
dp[0] = true;
for(int i=1;i<=n;i++){
for(auto word:wordDict){
int m = word.size();
if(i>=m&&s.substr(i-m,m)==word&&dp[i-m]) dp[i] = true;
}
}
return dp[n];
}
};
140优化未完待续
