讨论/《算法面试题汇总》 - 单词拆分/
《算法面试题汇总》 - 单词拆分

好家伙,活生生凑了个双dp才做出来,sort那行代码可以优化成for找到最小的长度,懒得改了

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        int m = wordDict.size();
        int n = s.size();
        vector<vector<int>> dp(n+1,vector<int>(m+1,0));
        vector<int> temp(n+1,0);
        sort(wordDict.begin(),wordDict.end(),[&](string x ,string y){
            if(x.size()<y.size()) return true;
            else return false;
        });
        dp[0][0] = temp[0] = true;
        if(wordDict[0] == s.substr(0,wordDict[0].size())){
            dp[wordDict[0].size()][1] = true;
        }
        for(int i = wordDict[0].size();i<= n;++i){
            for(int j = 1;j<=m ;++j){
                int len = wordDict[j-1].size();
                if(dp[i][j-1]){
                    temp[i] = true;
                    dp[i][j] = true;
                }
                if(len<=i&&temp[i-len]&&s.substr(i-len,len) == wordDict[j-1]){
                    dp[i][j] = true;
                    temp[i] = true;
                }
            }
        }
        return dp[n][m];
    }
};
展开全部 7 讨论