7. 单词拆分（LeetCode-139）
题目
给你一个字符串 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" 拼接成。 注意，你可以重复使用字典中的单词。
示例 3：
输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"] 输出: false
提示：
1 <= s.length <= 300
1 <= wordDict.length <= 1000
1 <= wordDict[i].length <= 20
s 和 wordDict[i] 仅有小写英文字母组成
wordDict 中的所有字符串 互不相同
思路
不会，卡尔哥的也没看懂。然后发现官方题解很清晰
我们定义 dp[i] 表示字符串 s 前 i 个字符组成的字符串s[0~i−1] 是否能被空格拆分成若干个字典中出现的单词。从前往后计算考虑转移方程，每次转移的时候我们需要枚举包含位置 i-1 的最后一个单词，看它是否出现在字典中以及除去这部分的字符串是否合法即可。公式化来说，我们需要枚举 s[0~i-1] 中的分割点 j ，看 s[0~j-1] 组成的字符串 S 1 （默认 j = 0 时 S 1 为空串）和 s[j~i-1] 组成的字符串 S 2 S_2S 2 是否都合法，如果两个字符串均合法，那么按照定义 S 1和 S 22拼接成的字符串也同样合法。由于计算到 dp[i] 时我们已经计算出了 dp[0~i−1] 的值，因此字符串 S 1 是否合法可以直接由 dp[j] 得知，剩下的我们只需要看 S 2 是否合法即可，因此我们可以得出如下转移方程
d p [ i ] = d p [ j ] & & c h e c k ( s [ j ∼ i − 1 ] )
五部曲
dp[i] 含义
表示字符串前 i 个字符组成的字符串s[0~i−1] 是否能被空格拆分成若干个字典中出现的单词
递推公式
d p [ i ] = d p [ j ] & & c h e c k ( s [ j ∼ i − 1 ] )
数组初始化
dp[0]=true 表示字符串为空，但题目中说了“给定⼀个非空字符串 s” 所以测试数据中不会出现i为0的情况，那么dp[0]初始为true完全就是为了推导公式。下标非0的dp[i]初始化为false，只要没有被覆盖说明都是不可拆分为⼀个或多个在字典中出现的单词。
遍历顺序
实在是没看懂，直接复制卡尔哥的原话了
题⽬中说是拆分为⼀个或多个在字典中出现的单词，所以这是完全背包。
还要讨论两层for循环的前后循序。
如果求组合数就是外层for循环遍历物品，内层for遍历背包。
如果求排列数就是外层for遍历背包，内层for循环遍历物品。
本题最终要求的是是否都出现过，所以对出现单词集合⾥的元素是组合还是排列，并不在意！
那么本题使⽤求排列的⽅式，还是求组合的⽅式都可以。
即：外层for循环遍历物品，内层for遍历背包 或者 外层for遍历背包，内层for循环遍历物品 都是可以的。
但本题还有特殊性，因为是要求⼦串，最好是遍历背包放在外循环，将遍历物品放在内循环。如果要是外层for循环遍历物品，内层for遍历背包，就需要把所有的⼦串都预先放在⼀个容器⾥。（如果不理解的话，可以⾃⼰尝试这么写⼀写就理解了）所以最终我选择的遍历顺序为：遍历背包放在外循环，将遍历物品放在内循环。内循环从前到后。
测试用例
代码展示
class Solution { public: bool wordBreak(string s, vector<string> &wordDict) { unordered_set<string> wordset(wordDict.begin(), wordDict.end()); vector<bool> dp(s.size() + 1, false); dp[0] = true; for (int i = 0; i <= s.size(); i++) { for (int j = 0; j < i; j++) { if (dp[j] && wordset.find(s.substr(j, i - j)) != wordset.end()) { dp[i] = true; break; } } } return dp[s.size()]; } };
