LeetCode 139. 单词拆分 —— 从暴力回溯到 DP 完全背包

LeetCode 139. 单词拆分 —— 从暴力回溯到 DP 完全背包

"给定一个字符串和一个单词字典，判断字符串能不能被拆成字典里的词"——听起来像字符串题，真正落地时却是 动态规划 / 记忆化搜索 的经典入门场景。它是 LeetCode 上「字符串 + DP」的标杆题，也是面试里考察「能不能把递归思维翻译成 DP 表」的常客。

为什么值得认真写？因为朴素回溯在最坏情况下是指数级的，而正确写出 O(n²) 的 DP 并不难——真正拉开差距的是：

坑点	表现	正确做法
重复子问题	同一后缀被反复拆，超时	记忆化 / 自底向上 DP
字典查找	每次 list.includes 是 O(m·L)	先转成 HashSet，均摊 O(L)
无意义枚举	枚举超长 / 空切分	用 单词最大长度 剪枝
下标边界	dp[i] 表示前 i 还是前 i+1	统一约定：dp[i] = s[0..i) 能否拆分

本文将从暴力回溯 → 记忆化搜索 → 自底向上 DP → 剪枝优化层层递进，重点讲透「完全背包」视角下的状态转移，并附 JavaScript / Python 双版本代码 + 完整推演。进阶还会点到 140. 单词拆分 II（输出所有拆法）。

---

问题描述

LeetCode 139. Word Break（单词拆分）

示例 1：

 复制代码输入：s = "leetcode", wordDict = ["leet", "code"]
输出：true
解释：返回 true，因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。

 复制代码s = "leetcode"
     ^^^^
     leet  ← 字典命中
         ^^^^
         code ← 字典命中
→ true

示例 2：

 复制代码输入：s = "applepenapple", wordDict = ["apple", "pen"]
输出：true
解释：返回 true，因为 "applepenapple" 可以由 "apple" + "pen" + "apple" 拼接成。
     注意，你可以重复使用字典中的单词。

示例 3：

 复制代码输入：s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出：false
解释：无论怎么切，末尾的 "og" 无法被字典覆盖。

约束条件：

• 1 <= s.length <= 300
• 1 <= wordDict.length <= 1000
• 1 <= wordDict[i].length <= 20
• s 和 wordDict[i] 仅由小写英文字母组成
• wordDict 中的所有字符串 互不相同

进阶思考（面试常问）：

1. 若要求输出所有合法拆分方案？→ 140. 单词拆分 II
2. 若字典极大、单词很长？→ Trie + DP
3. 这题和「完全背包」是什么关系？

---

核心思想

问题本质：前缀能否被字典「覆盖」

把字符串从左往右切，每一次切出的片段都必须在字典里。问的是：是否存在至少一种切法，把整个串切完。

 复制代码s = "applepenapple"
wordDict = {apple, pen}一种合法切法：
  [apple] [pen] [apple]
  0────5  5──8  8─────13另一种尝试（失败路径）：
  [app] ...  ← "app" 不在字典，此路不通

为什么会有大量重复计算？

暴力 DFS 在每个位置尝试所有可能的单词结尾：

 复制代码s = "aaaaaaa..."，字典含 "a", "aa", "aaa", ...从位置 0 出发：
  切 "a"  → 去拆后缀
  切 "aa" → 去拆后缀
  切 "aaa"→ 去拆后缀
  ...
同一后缀 "aaa...a" 会被无数条路径重复求解 → 指数爆炸

关键观察：「从下标 i 开始的后缀能否被拆分」只取决于 s[i..] 本身和字典，与「前面怎么走到 i」无关——这是最优子结构 + 无后效性，适合 DP / 记忆化。

状态定义（一锤定音）

 复制代码dp[i] = true  当且仅当  s[0..i)  可以被字典中的单词拼接而成          （左闭右开：前 i 个字符）边界：dp[0] = true   // 空串视为「已拆完」
答案：dp[n]

状态转移

要让 dp[i] = true，必须存在某个切分点 j < i，使得：

 复制代码dp[j] == true  且  s[j..i) ∈ wordDict

 复制代码s:  [  已合法前缀  |  候选单词  ]
     0 ········ j ··········· i
     ← dp[j] →   ← 字典查找 →若两者同时成立 → dp[i] = true

这其实就是 完全背包 的一维形式：

背包视角	本题映射
背包容量	字符串长度 n
物品	字典中的单词（可无限次使用）
恰好填满容量 i	前 i 个字符恰好被拆完
转移	枚举最后一个单词

---

思路分析

解法一：暴力回溯 DFS ⭐ 入门

核心思路： 从当前位置 start 出发，枚举所有可能的结束位置 end，若 s[start..end) 在字典中，则递归处理 end；若能走到 n，返回 true。

 复制代码dfs(start):
  if start == n: return true
  for end in start+1 .. n:
    if s[start..end) ∈ dict and dfs(end):
      return true
  return false

• 时间复杂度：最坏 O(2ⁿ)（每个位置都可切 / 不切）
• 空间复杂度：O(n) 递归栈

解法二：记忆化搜索（自顶向下 DP）⭐⭐ 推荐理解

在暴力基础上加一个数组 memo[start]：

 复制代码memo[start] =
  true  → 后缀 s[start..] 可拆
  false → 不可拆
  null  → 尚未计算

每个下标最多被完整计算一次，状态数 O(n)；若枚举所有结束位置并做子串哈希，朴素约 O(n³)。配合 Set + 长度剪枝（只枚举 end ∈ (start, start+maxLen]）可降到 O(n·L²)，L 为单词最大长。

为什么好讲： 先递归后填表，转移逻辑和暴力完全一致，只是「算过的不再算」。

解法三：自底向上 DP ⭐⭐⭐ 面试首选

按长度从小到大填 dp[0..n]：

 复制代码dp[0] = true
for i = 1 .. n:                  # 枚举右端（开区间）
  for j = 0 .. i-1:              # 枚举切分点
    if dp[j] and s[j..i) ∈ dict:
      dp[i] = true
      break                      # 找到一种即可
return dp[n]

• 时间：O(n³) 朴素 / O(n·L²) 优化后（L ≤ 20）
• 空间：O(n) + 字典 Set

解法四：长度剪枝 + 字典 Set 优化 ⭐⭐⭐ 实战最优

字典单词长度上限只有 20，没必要枚举所有 j：

 复制代码maxLen = max(word.length for word in wordDict)for i = 1 .. n:
  # 只枚举「最后一个单词」可能的起点
  for j = max(0, i - maxLen) .. i-1:
    if dp[j] and set.has(s[j..i)):
      dp[i] = true
      break

 复制代码优化效果：
  内层从 O(n) → O(maxLen) ≤ O(20)
  子串长度 ≤ 20，哈希查找更快
  总计 O(n · L · L) = O(n·L²)，远快于朴素双重循环

解法对比

解法	时间复杂度	空间复杂度	核心思想
暴力 DFS	O(2ⁿ)	O(n)	枚举所有切法
记忆化搜索（+剪枝）	O(n·L²)	O(n)	自顶向下，消除重复
自底向上 DP（+剪枝）	O(n·L²)	O(n)	前缀布尔覆盖
BFS（+剪枝）	O(n·L²)	O(n)	把下标当图节点

---

代码实现

JavaScript 版本

方法一：记忆化搜索

 复制代码/**
 * @param {string} s
 * @param {string[]} wordDict
 * @return {boolean}
 */
var wordBreak = function(s, wordDict) {
    const wordSet = new Set(wordDict);
    const n = s.length;
    // memo[i]: 从 i 开始的后缀能否拆分；undefined 表示未算
    const memo = new Array(n);    const dfs = (start) => {
        if (start === n) return true;
        if (memo[start] !== undefined) return memo[start];        for (let end = start + 1; end <= n; end++) {
            const word = s.slice(start, end);
            if (wordSet.has(word) && dfs(end)) {
                memo[start] = true;
                return true;
            }
        }
        memo[start] = false;
        return false;
    };    return dfs(0);
};

方法二：自底向上 DP + 长度剪枝 ⭐⭐⭐

 复制代码/**
 * @param {string} s
 * @param {string[]} wordDict
 * @return {boolean}
 */
var wordBreak = function(s, wordDict) {
    const wordSet = new Set(wordDict);
    const n = s.length;
    let maxLen = 0;
    for (const w of wordDict) {
        maxLen = Math.max(maxLen, w.length);
    }    // dp[i]：s 的前 i 个字符 s[0..i) 能否被拆分
    const dp = new Array(n + 1).fill(false);
    dp[0] = true;    for (let i = 1; i <= n; i++) {
        // 只考虑长度不超过 maxLen 的「最后一个单词」
        const left = Math.max(0, i - maxLen);
        for (let j = left; j < i; j++) {
            if (dp[j] && wordSet.has(s.slice(j, i))) {
                dp[i] = true;
                break;
            }
        }
    }    return dp[n];
};

方法三：BFS（下标图最短路视角）

把每个可达下标看作图节点，边为「一次字典单词匹配」：

 复制代码/**
 * @param {string} s
 * @param {string[]} wordDict
 * @return {boolean}
 */
var wordBreak = function(s, wordDict) {
    const wordSet = new Set(wordDict);
    const n = s.length;
    let maxLen = 0;
    for (const w of wordDict) maxLen = Math.max(maxLen, w.length);    const visited = new Array(n + 1).fill(false);
    const queue = [0]; // 从下标 0 出发
    visited[0] = true;    while (queue.length) {
        const start = queue.shift();
        if (start === n) return true;        // 枚举从 start 出发能匹配的单词
        for (let end = start + 1; end <= Math.min(n, start + maxLen); end++) {
            if (visited[end]) continue;
            if (wordSet.has(s.slice(start, end))) {
                visited[end] = true;
                queue.push(end);
            }
        }
    }
    return false;
};

Python 版本

方法一：记忆化搜索

 复制代码from functools import cache
from typing import Listclass Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        word_set = set(wordDict)
        n = len(s)        @cache
        def dfs(start: int) -> bool:
            if start == n:
                return True
            for end in range(start + 1, n + 1):
                if s[start:end] in word_set and dfs(end):
                    return True
            return False        return dfs(0)

方法二：自底向上 DP + 长度剪枝 ⭐⭐⭐

 复制代码from typing import Listclass Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        word_set = set(wordDict)
        n = len(s)
        max_len = max((len(w) for w in wordDict), default=0)        # dp[i]：s[:i] 能否被拆分
        dp = [False] * (n + 1)
        dp[0] = True        for i in range(1, n + 1):
            left = max(0, i - max_len)
            for j in range(left, i):
                if dp[j] and s[j:i] in word_set:
                    dp[i] = True
                    break        return dp[n]

方法三：BFS

 复制代码from collections import deque
from typing import Listclass Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        word_set = set(wordDict)
        n = len(s)
        max_len = max((len(w) for w in wordDict), default=0)        visited = [False] * (n + 1)
        q = deque([0])
        visited[0] = True        while q:
            start = q.popleft()
            if start == n:
                return True
            for end in range(start + 1, min(n, start + max_len) + 1):
                if visited[end]:
                    continue
                if s[start:end] in word_set:
                    visited[end] = True
                    q.append(end)        return False

---

逐步推演

示例 1：s = "leetcode", wordDict = ["leet", "code"]

 复制代码下标:  0 1 2 3 4 5 6 7 8
字符:  l e e t c o d e
dp 长度 = 9（dp[0]..dp[8]）
maxLen = 4
wordSet = {leet, code}

i	考察的 j 区间	命中情况	dp[i]
0	—	边界	true
1	j∈[0,0]	"l" ∉ dict	false
2	j∈[0,1]	"le","e" 均否	false
3	j∈[0,2]	均否	false
4	j∈[0,3]	j=0, "leet" ∈ dict 且 dp[0]	true
5	j∈[1,4]	"eetco"... 均否	false
6	j∈[2,5]	均否	false
7	j∈[3,6]	均否	false
8	j∈[4,7]	j=4, "code" ∈ dict 且 dp[4]	true

 复制代码dp:  [T, F, F, F, T, F, F, F, T]
      0  1  2  3  4  5  6  7  8关键两步：
  dp[4] = true  ← 前缀 "leet"
  dp[8] = true  ← 前缀 "leetcode" = "leet" + "code"答案 dp[8] = true 

 复制代码可视化：
  leet code
  ^^^^ ^^^^
  j=0  j=4
  →i=4 →i=8

示例 2：s = "applepenapple", wordDict = ["apple","pen"]

 复制代码s: a p p l e p e n a p p l e
   0 1 2 3 4 5 6 7 8 9 10 11 12 13
maxLen = 5

关键转移（只列 true 的位置）：

 复制代码dp[0]  = true
i=5:  j=0, s[0:5]="apple" ∈ dict → dp[5]=true
i=8:  j=5, s[5:8]="pen"   ∈ dict → dp[8]=true
i=13: j=8, s[8:13]="apple"∈ dict → dp[13]=truedp 真值位置: 0, 5, 8, 13
答案 true （单词可重复使用）

 复制代码[apple][pen][apple]
0─────5────8──────13

示例 3：s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]

 复制代码s: c a t s a n d o g
   0 1 2 3 4 5 6 7 8 9

可达前缀	一次合法转移	说明
dp[0]=T	—	空前缀哨兵
dp[3]=T	j=0, "cat"	前缀 cat
dp[4]=T	j=0, "cats"	前缀 cats
dp[7]=T	j=3, "sand"（或 j=4, "and"）	cat+sand / cats+and
dp[9]	无	从 7 出发 "o"/"og" 均不在字典

 复制代码dp: [T, F, F, T, T, F, F, T, F, F]
     0        3  4        7     9maxLen = 4（cats/sand/dog 中最长为 4）
从 7 出发只能试到 7+4=11，但 n=9，实际试：
  s[7:8]="o"  ∉ dict
  s[7:9]="og" ∉ dict
无法到达 9 → false 

 复制代码失败示意：
  cats and og   ← "og" 不在字典
  cat sand og   ← 同上
  cats ando g   ← 都不是字典词

记忆化搜索推演（同一例 "leetcode"）

 复制代码dfs(0):
  试 end=1.. "l","le","lee" 均不在字典
  试 end=4: "leet" ∈ dict → dfs(4)
    dfs(4):
      试 "c","co","cod" 否
      试 end=8: "code" ∈ dict → dfs(8)
        dfs(8): start==n → true
      ← true，memo[4]=true
    ← true，memo[0]=true
→ true若之后再次询问 dfs(4)，直接返回 memo[4]，不再枚举。

---

复杂度分析

方法	时间复杂度	空间复杂度	适用场景
暴力 DFS	O(2ⁿ)	O(n)	仅理解题意
记忆化搜索（+剪枝）	O(n·L²)	O(n)	递归思维清晰时
DP + 剪枝	O(n·L²)	O(n)	面试首选
BFS（+剪枝）	O(n·L²)	O(n)	偏好图论表述时

时间复杂度细节

 复制代码设 n = s.length，L = max word length，m = wordDict.lengthDP + Set + 剪枝：
  外层 i：n
  内层 j：最多 L 次（≤20）
  每次 slice + Set 查找：O(L)（哈希与子串长度相关）
  ────────────────
  总计：O(n · L · L) = O(n · L²)
  面试口述：L 很小，常直接说 O(n²)建 Set：O(m · L)

空间复杂度细节

 复制代码dp 数组：O(n)
wordSet：O(总字符数) ≤ O(m · L)
递归栈 / BFS 队列：O(n)

---

优化方向与实现细节

1. 为什么必须先转 Set？

查找方式	单次代价	n=300 时影响
wordDict.includes(sub)	O(m·L)	易 TLE
wordSet.has(sub)	均摊 O(L)	稳过
Trie 查询	O(L)	字典极大时更优

2. 枚举顺序：按终点切 vs 按单词枚举

两种等价写法：

 复制代码写法 A（本文）：枚举切分点 j，检查 s[j..i) 是否在字典写法 B：若 dp[i]=true，枚举字典中每个 word，尝试更新 dp[i+len]

写法 B 是更标准的「完全背包枚举物品」：

 复制代码// 写法 B 示意
dp[0] = true;
for (let i = 0; i < n; i++) {
    if (!dp[i]) continue;
    for (const word of wordDict) {
        const len = word.length;
        if (i + len <= n && s.startsWith(word, i)) {
            dp[i + len] = true;
        }
    }
}

	写法 A	写法 B
内层	切分点 / 长度	字典单词
适合	字典大、L 小	字典小
本题	L≤20，A 更稳	m≤1000，B 也可

3. 与完全背包的严格对应

 复制代码完全背包：dp[c] |= dp[c - w]   （物品体积 w 可重复选）
单词拆分：dp[i] |= dp[i - len] （且 s 对应片段 == word）差异：
  普通背包只关心「体积」，本题还要求「字符串内容匹配」
  → 多一次 s[j..i) === word 的校验

4. 容易踩的边界

边界	处理
空串 s	本题约束长度 ≥1；若放宽，应返回 true（dp[0]）
字典含空串	现行题面单词长度 ≥1；若有 ""，会死循环，需过滤
单字符全匹配	maxLen=1，剪枝仍正确
无法拆分	全程只有 dp[0]=true，返回 false

5. 扩展到 140：输出所有方案

139 只问「能不能」，140 要「所有拆法」：

 复制代码思路：
  1. 先跑一遍 139 的 dp，得到哪些前缀可达（剪枝用）
  2. 再 DFS/回溯拼路径：
       path + word，递归 end
  3. 仅当 dp[end]==true（后缀也可达）才继续 —— 避免无效分支注意：140 的 n≤20 更小，但方案数可能很多，需要回溯收集。

---

举一反三

本题在「字符串 DP」体系中的位置

 复制代码字符串拆分 / 覆盖类：
  ├── 139. 单词拆分        ← 判断能否覆盖（布尔 DP）
  ├── 140. 单词拆分 II     ← 输出所有覆盖方案（回溯 + DP 剪枝）
  ├── 472. 连接词          ← 词是否由其他词组成（Trie + DP）
  └── 1406. 石子游戏 III   ← 另一类「后缀决策」DP（关联思维）完全背包家族：
  ├── 322. 零钱兑换        ← 最少硬币数
  ├── 518. 零钱兑换 II     ← 组合数
  ├── 139. 单词拆分        ← 字符串版「能否凑成」
  └── 377. 组合总和 Ⅳ     ← 排列数

关联题目

题目	核心思想	与本题的关系
140. 单词拆分 II	回溯收集路径	直接升级版：bool → 所有方案
322. 零钱兑换	完全背包最小值	转移骨架相同，物品从「硬币」换成「单词」
472. 连接词	Trie + 单词拆分	对每个词做 139，字典是其余词
91. 解码方法	一维 DP 划分	「数字串按 1~26 划分」≈ 固定小字典的 139
132. 分割回文串 II	划分 + 回文判定	同样是「枚举最后一段」
127. 单词接龙	BFS 最短变码	同属「单词图」，但边是字母替换不是拼接

「划分型 DP」通用框架

 复制代码┌──────────────────────────────────────────────────┐
│  划分型 DP 通用思维框架：                            │
│                                                   │
│  1. 定义 dp[i] = 前缀 s[0..i) 的最优 / 可达性        ││                                                   ││  2. 枚举「最后一段」s[j..i)：                        ││       if 最后一段合法 and dp[j] 满足：               │
│           更新 dp[i]                               │
│                                                   │
│  3. 合法段判定：                                    │
│       字典查找 / 回文 / 数值范围 / 括号匹配 ...       │
│                                                   │
│  4. 剪枝：段长上界、预处理合法段表、Set/Trie          │
│                                                   │
│  5. 若需方案：DP 判可达 + DFS 回溯拼路径              │
└──────────────────────────────────────────────────┘

 复制代码// 划分型 DP 伪代码模板
function partitionDP(s, isValid /* (j,i) => bool */) {
    const n = s.length;
    const dp = new Array(n + 1).fill(/* 初始不可达 */);
    dp[0] = /* 空前缀的基值 */;    for (let i = 1; i <= n; i++) {
        for (let j = 0; j < i; j++) {
            if (/* dp[j] 可达 */ && isValid(j, i)) {
                // 更新 dp[i]：布尔 or / 数值 min/max/sum ...
            }
        }
    }
    return dp[n];
}

延伸思考（面试追问）

1. "单词可以重叠吗？" → 不可以。拆分是相邻拼接，不是子序列。s[j..i) 与 s[i..k) 首尾相接、互不重叠。
2. "字典词必须用完吗？" → 不必。题面明确：可不全部使用，可重复使用。
3. "和正则 / 通配匹配有何不同？" → 本题是精确单词集合；通配是模式匹配，状态设计不同。
4. "如何返回任意一种拆法？" → 额外记录 prev[i] = j（使 dp[i] 为 true 的某个 j），从 n 回溯到 0。
5. "字典有 10⁵ 个词怎么办？" → 建 Trie，转移时从 i 沿 Trie 往右扫，避免对每个 j 做字符串切片哈希。

---

总结

题目	难度	核心思想	推荐解法
139 单词拆分	Medium	前缀布尔 DP / 完全背包	Set + DP + 长度剪枝
140 单词拆分 II	Hard	DP 剪枝 + 回溯枚举方案	先 139 再 DFS

这道题的收获可以压成三句话：

1. 算法骨架：dp[i] 表示前 i 个字符能否拆分；枚举最后一段 s[j..i)，若在字典且 dp[j] 为真，则 dp[i]=true。

2. 实现命门：字典先变 HashSet；用 maxLen 剪枝 把内层从 O(n) 收到 O(L)；注意 dp[0]=true 空前缀哨兵。

3. 思维迁移：这是标准的 「划分型 DP」——和零钱兑换、解码方法、分割回文串同一套路，只是「最后一段合法」的判定换成了字典查找。

面试建议展示路径：

 复制代码先写暴力 DFS（证明懂拆分搜索树）
  → 指出同一后缀重复计算
  → 加 memo 变成记忆化搜索
  → 改写成自底向上 dp[i]
  → 主动优化：Set、maxLen 剪枝
  → 若被追问方案：说明 140 的「DP + 回溯」
  → 点明完全背包 / 划分型 DP 本质

---