当前位置： 移动技术网 > IT编程>网络>音视频 > Leetcode 139和140单词拆分：判断可行性以及输出方案

Leetcode 139和140单词拆分：判断可行性以及输出方案

2020年07月13日  | 移动技术网IT编程  | 我要评论

暴力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

您可能感兴趣的文章:

如对本文有疑问， 点击进行留言回复！！

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网