139. 单词拆分

题目描述

给定一个字符串 s 和一个字符串列表 wordDict，判断能否使用字典中的单词拼接出完整的 s。

字典中的单词可以重复使用，不要求每个单词都被使用。

示例：

输入：s = "leetcode", wordDict = ["leet", "code"]
输出：true
解释："leetcode" 可以拆分为 "leet" + "code"。

输入：s = "applepenapple", wordDict = ["apple", "pen"]
输出：true
解释："apple" 可以重复使用。

输入：s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出：false

1. 从“最后一个单词”理解问题

假设要判断前 i 个字符 s[0..i-1] 能否被拆分，可以枚举最后一个单词从位置 j 开始：

s[0..i-1] = s[0..j-1] + s[j..i-1]
             已拆分部分      最后一个单词

要让整个前缀可以拆分，必须同时满足：

s[0..j-1] 已经能够被字典单词拆分。
s[j..i-1] 本身是字典中的单词。

只要存在一个位置 j 同时满足这两个条件，前 i 个字符就可以拆分。

这就是本题动态规划转移的来源。

2. 状态定义

定义长度为 s.length + 1 的布尔数组：

dp[i]：字符串的前 i 个字符 s[0..i-1] 能否由字典单词拼接而成

特别注意，i 表示前缀长度，不是字符下标：

dp[0] 对应空字符串
dp[1] 对应 s.slice(0, 1)
dp[n] 对应整个字符串 s

因此最终答案是：

dp[s.length]

3. 为什么 `dp[0] = true`

初始化：

dp[0] = true;

这里不是说题目一定把空字符串视为一个字典单词，而是说：在还没有选取任何字符时，空前缀已经被成功拆分。

它相当于后续状态的起点。例如，如果 s.slice(0, 4) === "leet" 在字典中：

dp[4] = dp[0] && dictionary.has("leet")
      = true && true
      = true

如果 dp[0] 初始化为 false，第一个单词将永远无法建立任何可达状态，后续所有位置也都会是 false。

4. 状态转移方程

对于每个前缀终点 i，枚举最后一个单词的起点 j：

dp[i] = 存在某个 j，使得：
        dp[j] === true
        并且 s.slice(j, i) 在字典中

写成代码：

for (let i = 1; i <= s.length; i++) {
  for (let j = 0; j < i; j++) {
    if (dp[j] && dictionary.has(s.slice(j, i))) {
      dp[i] = true;
      break;
    }
  }
}

一旦找到合法的 j，就可以停止当前内层循环，因为本题只判断是否可拆分，不需要统计所有拆分方案。

5. 为什么必须先检查 `dp[j]`

仅仅发现 s.slice(j, i) 在字典中还不够，前面的 s.slice(0, j) 也必须能够被完整拆分。

例如：

s = "xleetcode"
wordDict = ["leet", "code"]

虽然 s.slice(1, 5) === "leet"、s.slice(5, 9) === "code" 都在字典中，但开头的 "x" 无法拆分，所以整个字符串仍然是 false。

dp[j] 表示位置 j 是一个真正可达的切分点。只有从可达位置出发找到字典单词，才能建立新的可达状态。

6. 为什么把词典转换为 `Set`

原始词典是数组。如果使用：

wordDict.includes(word)

每次判断都需要线性扫描词典。把它转换为 Set：

const dictionary = new Set(wordDict);

可以更直接地表达“某个单词是否存在”，查询的平均时间复杂度也更低。

7. 推荐代码实现

/**
 * @param {string} s
 * @param {string[]} wordDict
 * @return {boolean}
 */
var wordBreak = function (s, wordDict) {
  // 使用 Set 将单词查询优化为平均 O(1)。
  const dictionary = new Set(wordDict);

  // dp[i] 表示 s 的前 i 个字符能否由字典单词拼接而成。
  const dp = new Array(s.length + 1).fill(false);

  // 空字符串不需要选择任何单词，可以视为已经成功拆分。
  dp[0] = true;

  // i 是当前待判断前缀的长度，也是最后一个单词的结束位置。
  for (let i = 1; i <= s.length; i++) {
    // 枚举最后一个单词的起点 j。
    for (let j = 0; j < i; j++) {
      // 前 j 个字符可拆分，并且 s[j..i-1] 是字典单词，
      // 则前 i 个字符也可以拆分。
      if (dp[j] && dictionary.has(s.slice(j, i))) {
        dp[i] = true;

        // 本题只判断是否存在合法拆分，找到一种即可停止枚举。
        break;
      }
    }
  }

  // dp[s.length] 表示整个字符串能否被拆分。
  return dp[s.length];
};

这段代码和状态转移公式几乎完全一致：

dp[j] 为 true
+ s[j..i-1] 是字典单词
= dp[i] 为 true

第一次学习时不需要加入额外剪枝，先把 i 理解成当前前缀长度、把 j 理解成最后一个单词的起点即可。

8. 示例推演：`leetcode`

s = "leetcode"
wordDict = ["leet", "code"]

初始状态：

前缀长度 i   0 1 2 3 4 5 6 7 8
dp[i]         T F F F F F F F F

逐步计算：

`end`	检查到的有效切分	结果	原因
1	`"l"`	`false`	不在字典中
2	`"le"`	`false`	不在字典中
3	`"lee"`	`false`	不在字典中
4	`dp[0] + "leet"`	`true`	空前缀可达，`"leet"` 在字典中
5～7	没有合法切分	`false`	不能以完整字典单词结尾
8	`dp[4] + "code"`	`true`	前 4 个字符可拆分，`"code"` 在字典中

最终：

前缀长度 i   0 1 2 3 4 5 6 7 8
dp[i]         T F F F T F F F T

dp[8] === true，所以 "leetcode" 可以被拆分。

9. 失败示例：`catsandog`

s = "catsandog"
wordDict = ["cats", "dog", "sand", "and", "cat"]

可达前缀包括：

dp[0] = true
dp[3] = true    // "cat"
dp[4] = true    // "cats"
dp[7] = true    // "cat" + "sand"，或 "cats" + "and"

虽然末尾的 "dog" 在字典中，但它从位置 6 开始，而 dp[6] === false：

catsan | dog
       ^
这个切分点不可达

从可达位置 7 开始只剩下 "og"，它不在字典中。因此 dp[9] === false。

这个例子说明：找到字典单词只是转移的一半，还必须确认它前面的切分点可达。

10. 正确性说明

可以按照前缀长度进行归纳证明。

如果 `dp[i] === true`，前 `i` 个字符一定可以拆分

算法只会在某个 dp[j] === true 且 s.slice(j, i) 是字典单词时，把 dp[i] 设为 true。根据 dp[j] 的定义，前 j 个字符可以拆分；再拼接最后一个字典单词，就能拆分前 i 个字符。

如果前 `i` 个字符可以拆分，算法一定会得到 `dp[i] === true`

任取一种合法拆分，设最后一个单词从位置 j 开始。那么前 j 个字符也可以合法拆分，因此按照归纳假设 dp[j] === true；最后一个单词 s.slice(j, i) 在字典中。算法枚举到这个 j 时一定会把 dp[i] 设为 true。

因此，dp[i] 与“前 i 个字符可以拆分”等价，dp[s.length] 就是正确答案。

11. 复杂度分析

设 n 为字符串 s 的长度。

外层枚举前缀终点，执行 n 次。
内层枚举最后一个单词的起点，最多执行 n 次。
在常见算法分析中，把哈希集合查询视为平均 O(1)，因此通常将时间复杂度写为 O(n²)。
如果严格计入 JavaScript 中 slice 创建子串以及字符串哈希、比较的字符成本，单次候选检查最多需要 O(n)，最坏时间上界为 O(n³)。

空间复杂度：

dp 数组需要 O(n)。
哈希集合需要保存字典，共 O(D) 字符空间，其中 D 是字典所有单词的总字符数。
临时子串最多占用 O(n) 空间。

12. 可选优化：限制单词长度

基础版本已经足够清晰，也可以通过本题。如果希望减少无意义的切分检查，可以利用字典中的最长单词长度。

假设最长单词长度为 maxWordLength，那么最后一个单词不可能长于它。计算 dp[end] 时，起点无需从 0 开始，只需枚举：

max(0, end - maxWordLength) <= start < end

优化后的核心循环是：

const maxWordLength = Math.max(...wordDict.map((word) => word.length));

for (let end = 1; end <= s.length; end++) {
  const earliestStart = Math.max(0, end - maxWordLength);

  for (let start = earliestStart; start < end; start++) {
    if (dp[start] && dictionary.has(s.slice(start, end))) {
      dp[end] = true;
      break;
    }
  }
}

设最长单词长度为 L，候选检查次数可从 O(n²) 减少为 O(n × L)。这个剪枝不改变 DP 状态和转移逻辑，只缩小了起点枚举范围，因此更适合作为理解基础解法后的进一步优化。

13. 记忆化搜索写法

也可以把 start 定义为当前尚未拆分部分的起点，并使用 DFS 尝试每个字典单词：

var wordBreak = function (s, wordDict) {
  const memo = new Array(s.length).fill(undefined);

  const dfs = (start) => {
    if (start === s.length) {
      return true;
    }

    if (memo[start] !== undefined) {
      return memo[start];
    }

    for (const word of wordDict) {
      if (s.startsWith(word, start) && dfs(start + word.length)) {
        memo[start] = true;
        return true;
      }
    }

    memo[start] = false;
    return false;
  };

  return dfs(0);
};

如果没有 memo，同一个起点会被不同拆分路径反复搜索，最坏可能产生指数级分支。记忆化后，每个起点最多完整计算一次。

两种方法的视角不同：

自底向上 DP：判断哪些前缀长度可达。
记忆化搜索：判断从当前位置开始的后缀能否完成拆分。

14. 边界条件与易错点

边界条件：

字典单词可以重复使用，因此不能在匹配后从字典中删除单词。
wordDict 中没有重复单词，但即使转换为 Set 也不会影响结果。
一个单词可能就是完整的 s，此时通过 dp[0] 直接建立 dp[n]。
单词可以有公共前缀，例如 "car" 和 "cars"，算法必须保留所有可能的可达切分点。

易错点：

dp[i] 表示前 i 个字符，不是字符下标 i。
必须初始化 dp[0] = true。
JavaScript 的 slice(start, end) 不包含 end，正好对应前缀长度定义。
判断候选单词前必须确认 dp[start] === true。
不要使用贪心策略，例如每次选择最长或最短的匹配单词；局部选择可能阻断后续拆分。
使用普通 DFS 时必须增加记忆化，否则会重复计算同一后缀。

15. 为什么贪心不可靠

假设每次都选择当前能够匹配的最长单词，一旦后续失败，还需要回头尝试其他切分，因此本质上仍是搜索。

例如：

s = "cars"
wordDict = ["car", "ca", "rs"]

选择较长的 "car" 后只剩下 "s"，无法完成；选择 "ca" + "rs" 才能成功。

动态规划会同时保留所有可达前缀，不会因为一次局部选择而丢失正确答案。

16. 与完全背包的联系和区别

字典单词可以重复使用，因此本题有时被类比为“排列型完全背包”：

字符串长度类似背包容量。
字典单词类似可以重复选择的物品。
单词拼接顺序会影响能否匹配原字符串。

但本题不能只看单词长度。每次转移还必须检查对应位置的字符内容是否真的等于该单词，所以直接从“前缀可达性”理解通常更清楚。

17. 面试追问

如果需要返回一种合法拆分怎么办？

在把 dp[end] 设为 true 时，额外记录它来自哪个 start。计算结束后从 s.length 沿前驱位置反向回溯，即可恢复一种拆分方案。

如果需要返回所有合法句子怎么办？

这就是 LeetCode 140「单词拆分 II」。需要在搜索过程中记录所有可行选择，通常使用记忆化 DFS 返回每个后缀能够组成的所有句子。输出数量可能是指数级，不能只用布尔 DP 表示结果。

如果字典很大，如何继续优化？

可以使用字典树从每个可达位置开始沿字符串向后匹配，避免反复创建子串，也能在字符不匹配时尽早停止。代价是实现和额外数据结构更复杂。

18. 可迁移总结

本题最重要的思考方式是枚举最后一段：

前 i 个字符能否拆分
  = 是否存在一个切分点 j
    使前 j 个字符已经可拆分
    且 j 到 i 是一个合法单词

遇到字符串分段问题时，可以依次思考：

dp[i] 能否表示前 i 个字符的答案？
最后一段可能从哪里开始？
前面的切分点是否可达？
当前片段是否满足题目条件？

这套“可达前缀 + 合法最后一段”的模型也适用于解码方法、回文串分割、句子切分和字符串拼接等问题。

#139. 单词拆分

#题目描述

#1. 从“最后一个单词”理解问题

#2. 状态定义

#3. 为什么 dp[0] = true

#4. 状态转移方程

#5. 为什么必须先检查 dp[j]

#6. 为什么把词典转换为 Set

#7. 推荐代码实现

#8. 示例推演：leetcode

#9. 失败示例：catsandog

#10. 正确性说明

#如果 dp[i] === true，前 i 个字符一定可以拆分

#如果前 i 个字符可以拆分，算法一定会得到 dp[i] === true

#11. 复杂度分析

#12. 可选优化：限制单词长度

#13. 记忆化搜索写法

#14. 边界条件与易错点

#15. 为什么贪心不可靠

#16. 与完全背包的联系和区别

#17. 面试追问

#如果需要返回一种合法拆分怎么办？

#如果需要返回所有合法句子怎么办？

#如果字典很大，如何继续优化？

#18. 可迁移总结