跳至主要內容

LeetCode 139. 单词拆分

Skyme2026/8/5大约 5 分钟刷题Hot 100动态规划记忆化搜索字符串

LeetCode 139. 单词拆分

题目核心

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s。

  • 字典中的单词可以重复使用。
  • 字典中没有重复单词。
  • 拼接时字典中单词的顺序不重要，只要能拼出完整的 s 即可。

例如：

s = "leetcode", wordDict = ["leet", "code"]
返回 true（"leet" + "code"）

s = "applepenapple", wordDict = ["apple", "pen"]
返回 true（"apple" + "pen" + "apple"）

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

解题思考过程

第一步：理解问题

本质上是在问：能不能把 s 切成若干段，每一段都出现在字典里。

这其实是一个"分割"问题：从位置 0 开始，找一个前缀，如果前缀在字典里，剩下的部分再继续拆。

第二步：暴力递归

最直接的思路：从位置 start 开始，尝试所有可能的前缀 s[start...i]：

  • 如果前缀在字典里，递归判断剩下的部分 s[i...] 能不能拆。
  • 只要有一条路能拆到底（start == len），就返回 true。
canBreak(start):
  if start == len: return true
  for i from start+1 to len:
    if s[start..i] 在字典里 && canBreak(i):
      return true
  return false

这个思路是对的，但有大量重复计算：同一个 start 会被反复递归，时间复杂度是指数级。

第三步：记忆化优化

观察到：canBreak(start) 的结果只取决于 start，跟怎么到达 start 的无关。

所以可以用一个 memo 数组把每个 start 的结果存下来，下次再遇到直接返回，避免重复计算。

  • memo[start] == undefined：还没算过。
  • memo[start] == true/false：已经算过，直接返回。

加上记忆化后，每个 start 只计算一次，时间复杂度降为 O(n²)（n 是 s 的长度，每次切前缀 O(n)，Set 查找 O(1)）。

第四步：为什么用 Set 存字典

字典查找非常频繁，用 Set 可以做到 O(1) 查询，比数组的 includes（O(n)）快很多。

当前解法：DFS + 记忆化

/**
 * @param {string} s
 * @param {string[]} wordDict
 * @return {boolean}
 */
// dfs + 记忆化
var wordBreak = function (s, wordDict) {
  const len = s.length;
  const wordSet = new Set(wordDict);
  const memo = new Array(len);
  const canBreak = (start) => {
    if (start == len) return true;
    if (memo[start] != undefined) return memo[start];
    for (let i = start + 1; i <= len; i++) {
      const prefix = s.slice(start, i);
      if (wordSet.has(prefix) && canBreak(i)) {
        memo[start] = true;
        return true;
      }
    }
    memo[start] = false;
    return false;
  };
  return canBreak(0);
};

代码逐行解释

准备工作

const len = s.length;
const wordSet = new Set(wordDict);
const memo = new Array(len);
  • len：字符串长度，作为递归的终点判断。
  • wordSet：把字典转成 Set，O(1) 查询。
  • memo：记忆化数组，长度为 len，初始元素都是 undefined（表示未计算）。

canBreak 函数

const canBreak = (start) => {
  if (start == len) return true;

递归终点：如果 start 已经走到字符串末尾，说明前面所有段都成功拆分了，返回 true。

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

记忆化查询：如果这个 start 之前算过，直接返回记录的结果，不再重复计算。

  for (let i = start + 1; i <= len; i++) {
    const prefix = s.slice(start, i);

枚举前缀：从 start 开始，尝试所有长度的前缀 s[start...i]。i 从 start+1 到 len，覆盖所有可能的前缀。

    if (wordSet.has(prefix) && canBreak(i)) {
      memo[start] = true;
      return true;
    }
  }

核心判断：如果前缀在字典里，并且从 i 开始的剩余部分也能拆分（递归），那么从 start 开始就能拆分。

注意这里用了短路求值 &&：只有前缀在字典里，才会递归判断剩余部分，减少不必要的递归。

一旦找到一条成功路径，立即记录并返回 true（只需找到一种拆法）。

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

全部失败：如果所有前缀都试过了都不行，记录 memo[start] = false，返回 false。

启动递归

return canBreak(0);

从位置 0 开始判断整个字符串能否拆分。

执行过程示例

以 s = "leetcode", wordDict = ["leet", "code"] 为例：

canBreak(0):
  i=4, prefix="leet", 在字典里
    → 递归 canBreak(4):
        i=8, prefix="code", 在字典里
          → 递归 canBreak(8):
              start == len(8), 返回 true
        memo[4] = true, 返回 true
  memo[0] = true, 返回 true

最终返回 true

失败的例子 s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]：

canBreak(0):
  i=3, prefix="cat", 在字典里
    → canBreak(3):  剩余 "sandog"
        i=7, prefix="sand", 在字典里
          → canBreak(7): 剩余 "og"
              "o" "og" 都不在字典里
              memo[7] = false, 返回 false
        继续找其他前缀... 都失败
        memo[3] = false, 返回 false
  i=4, prefix="cats", 在字典里
    → canBreak(4):  剩余 "andog"
        i=7, prefix="and", 在字典里
          → canBreak(7): memo[7] 已是 false，直接返回 false
        ... 都失败
        memo[4] = false, 返回 false
  ... 其他前缀都失败
  memo[0] = false, 返回 false

最终返回 false

可以看到 memo[7] 在第二次遇到时直接返回，没有重复计算——这就是记忆化的价值。

复杂度分析

  • 时间复杂度：O(n²)。共有 n 个 start 状态，每个状态最多枚举 n 个前缀，每次切片和 Set 查询都是 O(n) 切片 + O(1) 查询，所以是 O(n²)（如果算上 slice 的 O(n) 则为 O(n³)，但通常按 O(n²) 状态数理解）。
  • 空间复杂度：O(n)。memo 数组 + 递归栈深度，都是 O(n)。

补充：动态规划解法

记忆化搜索是从前往后递归，也可以改成自底向上的动态规划。

定义 dp[i] 表示 s[0...i-1]（前 i 个字符）能否被拆分：

var wordBreak = function (s, wordDict) {
  const wordSet = new Set(wordDict);
  const dp = new Array(s.length + 1).fill(false);
  dp[0] = true; // 空串可以拆分

  for (let i = 1; i <= s.length; i++) {
    for (let j = 0; j < i; j++) {
      if (dp[j] && wordSet.has(s.slice(j, i))) {
        dp[i] = true;
        break;
      }
    }
  }
  return dp[s.length];
};
  • dp[0] = true：空串视为可拆分（递归的 start == len 终点对应这里）。
  • dp[i]：只要存在一个 j，使得 dp[j] 为 true 且 s[j...i] 在字典里，dp[i] 就是 true。

两种写法本质相同，记忆化搜索是自顶向下，动态规划是自底向上。

路的尽头依旧是路
Copyright © 2026 Skyme