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

暴力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优化未完待续