代码随想录算法训练营第四十天|139.单词拆分，多重背包，背包问题

139. 单词拆分 - 力扣（LeetCode）

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

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

示例 1：

输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。

示例 2：

输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple"可以由 "apple" "pen" "apple" 拼接成。注意，你可以重复使用字典中的单词。

思路：完全背包问题，单词就是物品，字符串s就是背包，单词能否组成字符串s，就是问物品能不能把背包装满。转换成背包问题有两个难点：①dp[i]是如何来的，②遍历顺序。

解决：动态规划五步曲

1.确定dp[j]的含义；

dp[i] : 字符串长度为i的话，dp[i]为true，表示可以拆分为一个或多个在字典中出现的单词。

2.确定dp[j]递推公式；

这里递推公式好像和之前不同，这里既没有01背包的价值，又没有完全背包的组合数量，通过dp[j]的含义我们知道，dp[i]要不就是true，要不就是false，我们要的就是true。

如果确定dp[j] 是true，且 [j, i] 这个区间的子串出现在字典里，那么dp[i]一定是true。（j < i ）。所以递推公式是 if([j, i] 这个区间的子串出现在字典里 && dp[j]是true) 那么 dp[i] = true。

到这里有点懵了，i是字符串长度，那j是什么，j这里其实表示当前遍历字符串中的位置。

举个例子：s = "leet", wordDict = ["le", "et"]

i等于1时，j就从0开始，j=0时，截取i-j就是le，发现wordDict中有“le”，所以dp[i]=true。

3.确定dp初始化；

没开始前，dp[i]=false，但是从递推公式中可以看出，dp[i] 的状态依靠 dp[j]是否为true，那么dp[0]就是递推的根基，dp[0]一定要为true，否则递推下去后面都都是false了

4.确定遍历顺序；

从上面分析可知，随着字符串长度i增大，依次遍历，能在wordDict中找到的单词肯定越多，结果也越有可能是true。，所以本题一定是先遍历背包，再遍历物品。

举个例子：拿 s = "applepenapple", wordDict = ["apple", "pen"] 举例。

"apple", "pen" 是物品，那么我们要求物品的组合一定是 "apple" + "pen" + "apple" 才能组成 "applepenapple"。"apple" + "apple" + "pen" 或者 "pen" + "apple" + "apple" 是不可以的，那么我们就是强调物品之间顺序。

5.举例推导dp数组。

以输入: s = "leetcode", wordDict = ["leet", "code"]为例，dp状态如图：

代码：这里利用unordered_set判断是否在wordDict中找到单词。

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        vector<bool> dp(s.size()+1,false);
        unordered_set<string> wordSet(wordDict.begin(), wordDict.end());
        dp[0]=true;
        for(int i=0;i<=s.size();i++){
            for(int j=0;j<i;j++){
                string word = s.substr(j, i - j); //substr(起始位置，截取的个数)
                if(wordSet.find(word) != wordSet.end()&&dp[j]){//dp[j]表示前j个长度的字符串可以由单词拼接，并且截取的子字符串在数组中
                    dp[i]=true;
                }
            }
        }
        return dp[s.size()];
    }
};