Leetcode 139和140单词拆分:判断可行性以及输出方案
程序员文章站
2022-03-02 10:12:00
暴力DFS超时,时间复杂度指数量级class Solution {public: bool flag; bool wordBreak(string s, vector& wordDict) { dfs(s,0,wordDict); return flag; } void dfs(string s, int start, vector& wordDict){ .....
暴力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优化未完待续
本文地址:https://blog.csdn.net/wwxy1995/article/details/107302979
上一篇: 链表中倒数第k个结点
下一篇: XML指南——XML 属性