[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

这道题最暴力的想法是，我们可以直接用回溯法来解。

遍历所有字典，当发现字典匹配字符串的前缀时，去掉该前缀，并拿剩余字符串，用字典进行递归匹配。

直到剩余字符串等于字典中某一单词时，说明字符串完全匹配。此时返回true。

function wordBreak(s: string, wordDict: string[]): boolean {
  let res = false;
  for (let i = 0; i < wordDict.length; i++) {
    if (res) return true;
    backtrack(s, i);
  }
  return res;

  function backtrack(str: string, index: number) {
    const word = wordDict[index];
    // 剩余字符串不以word开头，剪枝
    if (str.indexOf(word) !== 0) return;
    // 匹配完毕
    if (str === word) {
      res = true;
      return;
    }

    for (let i = 0; i < wordDict.length; i++) {
      backtrack(str.slice(word.length), i);
    }
  }
}

但这样做相当暴力，会直接导致栈溢出。我们需要找到一个更好复杂度的解法。

我们发现该题实际上是一个背包问题，并且是一个完全背包问题。

其存在最优子问题。即我们可以从后往前推导，若一个单词与等长字符串尾缀相等时，且去除尾缀后的字符串能够被字典拼出，则该字符串能被字典拼出。

因此我们设 dp[i] 表示字符串s的前 i 位是否可以用字典中的单词表示。

对于字典中的每一个词word，想办法找出dp[i]与dp[i-word.length]的关系。

1. 若i < word.length，则一定是无解的

2. 若截取子序列尾部能匹配字典中的单词，并且dp[n-word.length]有解，则该子序列有解，解为：dp[n-word.length]的解加上当前匹配单词

特殊的，当s为空时，任何情况下都匹配，即dp[0]=true

状态转移方程：dp[i] = dp[i - word.length] && s.substring(i - word.length, i) === word

function wordBreak(s: string, wordDict: string[]): boolean {
  const dp = Array(s.length + 1).fill(0);
  dp[0] = 1;

  for (let i = 1; i <= s.length; i++) {
    for (const word of wordDict) {
      // 剪枝
      if (i < word.length) continue;

      const tempWord = s.substring(i - word.length, i);
      if (tempWord === word && dp[i - word.length]) {
        dp[i] = 1;
        break;
      }
    }
  }

  return dp[s.length];
}