leetcode 139.单词拆分

思路：DP。

我们可以这样想，让dp数组代表长度为i时可不可以组成字符串。

OK，比如那里面的样例做个例子，leetcode，字典里面有leet,code，这显然是可以组成的。那么怎么才能用dp数组表现出这个意思呢？

我们可以这样想：如果我们把原先的字符串拆分成两段，一个一个枚举其中的断点，比如我们断成l,eetcode;le,etcode等等，这样一直断，直到我们能够拆分成字典里面的字符。

如果全部断点都枚举完了，还是没有找到，说明并不能用字典里面的数来拼成这个字符串。

注意：这里用了哈希表来查找字典元素比较方便，用了unordered_set容器，这个容器特别的地方在于它的使用函数上，它的find()如果找不到元素，就会返回它的end()，找到了就不会返回这个东西，所以在判断的时候如果说是.find()!=.end()说明我们能够找到里面的元素。

代码里有详细过程：

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        int n=wordDict.size();
        unordered_set<string>haha(n+1);
        int m=s.size();
        vector<bool>dp(m+1,0);
        dp[0]=true;//0个元素肯定是成功的，不需要拼接
        for(int i=0;i<n;i++)
        haha.insert(wordDict[i]);//插入字典到哈希表里面
        for(int i=1;i<=m;i++){//枚举长度
            for(int j=0;j<i;j++){//枚举在这个长度中的断点
                if(dp[j]&&haha.find(s.substr(j,i-j))!=haha.end()){//如果存在[0,j-1]子串并且[j,i]也存在，说明可以
                    dp[i]=true;
                }
            }
        }
        return dp[m];

    }
};

原文地址：https://blog.csdn.net/m0_73917165/article/details/137288119

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！