题目

题目来源：力扣（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”。
注意你可以重复使用字典中的单词。

示例 3：

输入: s = “catsandog”, wordDict = [“cats”, “dog”, “sand”, “and”, “cat”]
输出: false

思路分析

动态规划

根据题意，使用完全背包策略求解这道题。

1、状态定义
dp[i]：字符串长度为 i 的话，dp[i] 为true，表示可以拆分为一个或多个在字典wordDict中出现的单词。

2、确定递推公式
如果确定 dp[j] 为 true，即前 j 个字符经过拆分的子串存在于字典wordDict中，且 [i, j] 这个区间的子串存在于字典wordDict中，那么 dp[i] 一定是 true 。这里 j < i 。

所以递归公式为：dp[i]=dp[j] && wordDict.includes(s.substring(j + 1, i + 1));

3、状态初始化
从递推公式中可以看出，dp[i] 的状态依赖于 dp[j] 是否为 true，那么dp[0]就是递推的根基，dp[0]一定要为true，否则递归下去后面都是 false 了。

dp[0]表示如果字符串为空的话，说明出现在字典里。

下标非0的dp[i]初始化为false，只要没有被覆盖说明都是不可拆分为一个或多个在字典中出现的单词。

4、确定遍历顺序
题目中说是拆分为一个或多个在字典中出现的单词，所以这是完全背包。

如果求组合数就是外层for循环遍历物品，内层for遍历背包。 如果求排列数就是外层for遍历背包，内层for循环遍历物品。

本题采用 外循环遍历背包(字符串)，内循环遍历物品(单词)，且内循环从前往后遍历。

代码实现

  1. /**
  2.  * @param {string} s
  3.  * @param {string[]} wordDict
  4.  * @return {boolean}
  5.  */
  6. var wordBreak = function (s, wordDict) {
  7.   // dp[i]表示0-i之间的字符串是否可以被拆分并满足题设条件存在于wordDict中
  8.   let dp = new Array(s.length).fill(false);
  9.   let set = new Set(wordDict);
  10.   for (let i = 0; i < s.length; i++) { // 遍历背包(字符串)
  11.     // 检查0-i之间的字符串是否直接存在于wordDict中
  12.     if (set.has(s.substring(0, i + 1))) {
  13.       dp[i] = true;
  14.       continue;
  15.     }
  16.     // 这一步是为了检查。假如s.substring(0,i)不直接存在于wordDict中
  17.     // 那么判断拆分之后是否存在于wordDict中
  18.     for (let j = 0; j < i; j++) { // 遍历物品(单词)
  19.       // 递推公式 dp[j] && set.has(s.substring(j + 1, i + 1))
  20.       if (dp[j] && set.has(s.substring(j + 1, i + 1))) {
  21.         //如果dp[i]为true，说明前i个字符串结果拆解可以让他的所有子串
  22.         //都存在于字典wordDict中，直接终止内层循环，不用再计算dp[i]了。
  23.         dp[i] = true;
  24.         break;
  25.       }
  26.     }
  27.   }
  28.   return dp[s.length - 1]
  29. };

参考阅读 https://leetcode-cn.com/problems/word-break/solution/dai-ma-sui-xiang-lu-139-dan-ci-chai-fen-50a1a/ https://leetcode-cn.com/problems/word-break/solution/shu-ju-jie-gou-he-suan-fa-dong-tai-gui-h-3xkv/ https://leetcode-cn.com/problems/word-break/solution/yi-tao-kuang-jia-jie-jue-bei-bao-wen-ti-kchg9/