🔠139.单词拆分

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。

注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

思路

基本思想

单词可以重复使用，也就意味着本题是一个完全背包问题，并且只要出现一种方案即可返回true

最简单的办法就是是由for循环嵌套，wordDict有多少元素就嵌套多少层for循环，但是会超时

不仅是完全背包，而且还是一个排列问题，因为applepenapple拆分之后一定要是apple+pen+apple，而不是apple+apple+pen或者pen+apple+apple，所以这三种情况不同，也就是排列问题

最后确定递推公式，这种分割字符串的问题没有正常的递推公式，而是判断当前单词是否在wordDict 中，并且当前单词之前的部分是否可以由wordDict 拼接成，那么当前的字符串可以返回bool，就这样一直向后，最终返回s的结果

执行流程

1. 初始化dp数组全为false，并且为了查找当前单词是否在wordDict 中，将wordDict 存储到set中
2. dp[0]=true
3. 判断当前单词是否在wordDict 中，并且当前单词之前的部分是否可以由wordDict 中的单词拼接得到，如果可以的话当前字符串为true
4. 最后返回s的结果

代码

根据以上分析，得出以下代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        set<string> wordSet(wordDict.begin(),wordDict.end());
        vector<bool> dp(s.size()+1,false);
        dp[0]=true;
        for(int j=0;j<=s.size();++j){//遍历背包容量，也就是字符串的
            for(int i=0;i<j;++i){//遍历单词，不断将当前字符串拆分成不同的单词
                string word = s.substr(i,j-i);
                //当前单词在wordDict中，并且之前的部分可以由wordDict中的单词组成
                if(wordSet.find(word)!=wordSet.end()&&dp[i]){
                    dp[j]=true;
                }
            }
        }
        return dp[s.size()];
    }
};

总结

主要是懂得如何将字符串拆分，只要当前拆分的部分在wordDict中，并且之前的部分也可以由wordDict中的部分组成，那么当前字符串就可以由wordDict中的单词组成，也就可以返回true

这样慢慢往后，后面的用到前面的结果，动态规划最终得到字符串s的结果