码上秃的前端博客

Appearance

单词拆分I ​

Leetcode 139.单词拆分

题目描述 ​

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。

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

示例 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 中的所有字符串 互不相同

解题思路 ​

回溯解法 ​

不断的回溯所有的词典单词，拼成后返回 true，否则返回 false。

js
/**
* @param {string} s
* @param {string[]} wordDict
* @return {boolean}
*/
var wordBreak = function (s, wordDict) {
 // 是否能组合为 s
 let canCombine = false;
 function backtrack(str) {
   // 递归停止条件
   if (str === "") {
     canCombine = true;
     return;
   }
   for (const dict of wordDict) {
     if (str.startsWith(dict)) {
       // 回溯子问题
       backtrack(str.slice(dict.length));
     }
   }
 }
 backtrack(s);
 // 返回答案
 return canCombine;
};

这个解法部分用例是无法通过的，因为某些特殊用例，会出现很多重复的子问题计算。比如 aaaab 和 [a,aa,aaa,aaa]

两次回溯 第一个单词 a 和一次回溯第二个单词 aa，他两剩余的子问题是相同的，但是没有缓存结果，我们需要缓存这个结果，当遇到相同的子问题时，直接返回缓存的结果。

动态规划解法 ​

动态规划的思路是，我们等待一次拼成的结果，如果子问题无法拼成，缓存 false，能够拼成，缓存 true。

js
/**
 * @param {string} s
 * @param {string[]} wordDict
 * @return {boolean}
 */
var wordBreak = function (s, wordDict) {
  // 备忘录 dp
  const dp = new Array(s.length).fill(null);
  // i 是字符串下标
  function backtrack(i) {
    // 下标逼近最后一个，说明可以拼成
    if (i === s.length) return true;
    // 访问缓存
    if (dp[i] !== null) return dp[i];
    // 遍历  凑成区间 i - j
    for (let j = i + 1; j <= s.length; j++) {
      const subStr = s.slice(i, j);
      // 如果 i - j 这个区间有词典单词，并且子问题可以拼成，则可以拼成
      if (wordDict.includes(subStr) && backtrack(j)) {
        dp[i] = true;
        return true;
      }
    }
    // 如果能走到这里，肯定没有匹配的前缀，则缓存 false
    dp[i] = false;
    return false;
  }
  return backtrack(0);
};