336 lines
13 KiB
Markdown
336 lines
13 KiB
Markdown
---
|
||
tags: [算法/动态规划, 字符串DP, 哈希表优化]
|
||
create time: 2026-05-16 19:30
|
||
---
|
||
|
||
# 139. 单词拆分（Word Break）
|
||
|
||
> [!quote] LeetCode 原题 · 中等
|
||
> 给你一个字符串 `s` 和一个字符串列表 `wordDict` 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 `s`，则返回 `true`。
|
||
>
|
||
> **不要求**字典中出现的单词全部都使用，并且字典中的单词可以重复使用。
|
||
>
|
||
> - 输入范围：`1 <= s.length <= 300`，`1 <= wordDict.length <= 1000`，`1 <= wordDict[i].length <= 20`
|
||
> - `s` 和 `wordDict[i]` 仅由小写英文字母组成
|
||
> - `wordDict` 中的所有字符串互不相同
|
||
|
||
## 题面
|
||
|
||
**示例 1：**
|
||
|
||
```
|
||
输入：s = "leetcode", wordDict = ["leet", "code"]
|
||
输出：true
|
||
解释："leetcode" 可以由 "leet" 和 "code" 拼接成。
|
||
```
|
||
|
||
**示例 2：**
|
||
|
||
```
|
||
输入：s = "applepenapple", wordDict = ["apple", "pen"]
|
||
输出：true
|
||
解释："applepenapple" 可以由 "apple" "pen" "apple" 拼接成（单词可重复使用）。
|
||
```
|
||
|
||
**示例 3：**
|
||
|
||
```
|
||
输入：s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
|
||
输出：false
|
||
解释：虽然 "cats"、"dog" 等都能匹配到部分子串，但无法完整拼出整个字符串。
|
||
```
|
||
|
||
## 思路
|
||
|
||
### 第一步：识别问题模型
|
||
|
||
> [!question] 💡 思考
|
||
> 把字符串从某个位置切开——左边能用字典拼出来，右边恰好也是一个字典里的词——整段就能拼出来。这种"大问题拆成更小的同类子问题"的结构，指向哪类经典算法模型？
|
||
|
||
没错，这是 **线性 DP + 枚举分割点** 的经典范式。核心直觉：
|
||
|
||
> 要判断前 i 个字符能否被拆分，我们只需枚举最后一个词的起始位置 j —— 如果前 j 个字符能拆，且第 j+1 到第 i 个字符组成的子串在字典里，那么前 i 个字符也能拆。
|
||
|
||
### 第二步：定义状态与转移方程
|
||
|
||
定义状态：
|
||
|
||
> `dp[i]` = 字符串 `s` 的前 i 个字符能否用字典中的词拼接（布尔值）
|
||
|
||
状态转移：
|
||
|
||
> **`dp[i] = OR(dp[j] && s[j..i-1] ∈ wordDict)`**，对所有 `0 ≤ j < i`
|
||
|
||
其中 `s[j..i-1]` 表示从索引 j 开始、长度为 i-j 的子串。
|
||
|
||
```mermaid
|
||
flowchart TD
|
||
subgraph "dp[8] 的拆解过程 s = 'leetcode'"
|
||
A["dp[8]\n='leetcode'是否能拆分?"] --> B["j=0:\ndp[0]&&s[0..7]='leetcode'\nT && 不在字典 → ✗"]
|
||
A --> C["j=4:\ndp[4]&&s[4..7]='code'\nT && 在字典 ✓"]
|
||
A --> D["j=其他位置\n均无法同时满足两个条件\n→ ✗"]
|
||
B --> E["dp[8]=✗暂不成立"]
|
||
C --> F["dp[8]=✓\n找到一种可行拆分!\nleet + code"]
|
||
D --> G["继续检查..."]
|
||
F --> H["结果为 true ✅"]
|
||
end
|
||
|
||
style A fill:#e7f3ff,stroke:#3b82f6
|
||
style C fill:#dcfce7,stroke:#16a34a
|
||
style F fill:#dcfce7,stroke:#16a34a
|
||
style H fill:#dcfce7,stroke:#16a34a
|
||
```
|
||
|
||
> [!note] 📝 为什么这样是正确的？
|
||
> 因为每个合法拆分都可以唯一地看作"前面若干个词 + 最后一个词"的结构。我们枚举的就是这个"最后一个词"的起始位置。只要存在一种枚举使得两边都满足条件，答案就是 true。这体现了最优子结构性质——即使这里是布尔值而非数值。
|
||
|
||
### 第三步：确定边界条件
|
||
|
||
| 情况 | dp 值 | 理由 |
|
||
|------|-------|------|
|
||
| `dp[0]` | **true** | 空字符串显然可以被拆分——它是所有状态的"起点"。没有它为 false，递推就无法启动。 |
|
||
| 其他 `dp[i]` | **false** | 初始化为不可达，只有在找到有效拆分时才翻转为 true。 |
|
||
|
||
> [!warning] ⚠️ 关键细节：dp[0] = true
|
||
> 很多初学者会把 dp[0] 设为 false，这是致命错误。考虑 s = "leet", wordDict = ["leet"]——如果 dp[0] = false，那么 dp[4] 永远无法变为 true，因为唯一合法的拆分就是 dp[0] && "leet"。
|
||
|
||
### 第四步：自底向上填表
|
||
|
||
以 `s = "applepenapple", wordDict = ["apple", "pen"]` 为例，逐步走一遍：
|
||
|
||
| i | 子串 s[0..i) | 可能的 j | 判定过程 | dp[i] |
|
||
|---|-------------|---------|---------|-------|
|
||
| 0 | "" | — | 边界 | **true** |
|
||
| 1 | "a" | j=0 | dp[0] && "a" → T && ✗ | **false** |
|
||
| 2 | "ap" | j=0,1 | 均无匹配 | **false** |
|
||
| 3 | "app" | j=0,1,2 | 均无匹配 | **false** |
|
||
| 4 | "appl" | j=0,1,2,3 | 均无匹配 | **false** |
|
||
| 5 | "apple" | j=0…4 | j=0: dp[0]&&"apple" → **T && ✓** | **true** ← 第一个匹配的完整词！ |
|
||
| 6 | "applep" | j=0…5 | j=5: dp[5]&&"p" → T && ✗ | **false** |
|
||
| 7 | "applepe" | j=0…6 | j=5: dp[5]&&"pe" → T && ✗ | **false** |
|
||
| 8 | "applepen" | j=0…7 | j=5: dp[5]&&"pen" → **T && ✓** | **true** ← apple + pen |
|
||
| 9 | "applepena" | j=0…8 | 均无新增匹配 | **false** |
|
||
| 10 | "applepenap" | j=0…9 | 均无新增匹配 | **false** |
|
||
| 11 | "applepenapp" | j=0…10 | 均无新增匹配 | **false** |
|
||
| 12 | "applepenappl" | j=0…11 | 均无新增匹配 | **false** |
|
||
| 13 | "applepenapple" | j=0…12 | j=8: dp[8]&&"apple" → **T && ✓** | **true** ← apple + pen + apple |
|
||
|
||
```mermaid
|
||
flowchart LR
|
||
A["dp[0]=true\n''"] -->|"加 apple"| B["dp[5]=true\n'apple'"]
|
||
B -->|"加 pen"| C["dp[8]=true\n'applepen'"]
|
||
C -->|"加 apple"| D["dp[13]=true\n'applepenapple' ★答案"]
|
||
|
||
style A fill:#f3f4f6,stroke:#6b7280
|
||
style B fill:#fef3c7,stroke:#f59e0b
|
||
style C fill:#fef3c7,stroke:#f59e0b
|
||
style D fill:#dcfce7,stroke:#16a34a
|
||
```
|
||
|
||
> 表中展示了**成功路径上的关键节点**。实际上在计算每个 dp[i] 时，算法会尝试所有 j 值，而不仅仅是这条成功路径上的跳跃点。
|
||
|
||
## 代码提示
|
||
|
||
在动手写代码之前，想一想这些关键决策点：
|
||
|
||
> [!question] 💡 思考 1
|
||
> 内层循环需要遍历所有 j < i，每次都要判断 `s[j..i-1]` 是否在字典中。Go 语言中怎么快速判断一个子串是否存在于集合中？
|
||
|
||
可以用 `map[string]bool` 将字典构建成 O(1) 查找的哈希集合。然后用 Go 的切片操作 `s[j:i]` 提取子串并直接 map 查询。
|
||
|
||
> [!question] 💡 思考 2
|
||
> 外层遍历 i 和内层遍历 j 的顺序能调换吗？先枚举 j 再枚举 i 是否仍然正确？
|
||
|
||
不行。因为计算 `dp[i]` 时需要依赖所有 `dp[j]`（j < i）的结果，必须保证子问题的结果已被计算完毕。所以外层必须是 i，内层是 j。这也决定了这是一个**自底向上**的填表顺序。
|
||
|
||
## 技巧
|
||
|
||
### 提前终止优化
|
||
|
||
> [!tip] ⚡ 小优化：一旦 dp[n] 为 true 就可以提前退出
|
||
>
|
||
> 如果在填表过程中发现 `dp[s.Len()] == true`，说明已经找到了可行解，可以直接返回，无需继续计算后续无关状态。这在大部分可解案例中能节省不少时间。
|
||
|
||
### 最大词长剪枝
|
||
|
||
> [!tip] ⚡ 进阶优化：j 的范围可以限制在 `[i-maxLen, i)` 之间
|
||
>
|
||
> 字典中最长单词的长度是 maxLen。任何超过 maxLen 的子串都不可能在字典中找到。因此 j 不必从 0 开始枚举，而是从 `max(0, i-maxLen)` 开始即可。
|
||
>
|
||
> 结合题目约束 `maxLen ≤ 20`，内层循环最多只遍历 20 次，而不是 i 次。对于长字符串效果显著。
|
||
|
||
### Trie（前缀树）视角
|
||
|
||
> [!abstract] 🔍 进阶视角：从后往前用 Trie 加速
|
||
>
|
||
> 另一种思路是从右往左用 Trie 匹配：对每个 i，沿着 Trie 从 s[i] 开始往下走，每到一个标记为"单词结尾"的节点 k，就检查 `dp[k]` 是否为 true。这样可以跳过大量无效的子串比对。
|
||
>
|
||
> 空间代价更高（需要构建 Trie），但在字典很大、字符串很长的场景下优势明显。面试中推荐先用哈希表方案，如需优化再提 Trie。
|
||
|
||
| 方法 | 时间 | 空间 | 评价 |
|
||
|------|------|------|------|
|
||
| 哈希表 + DP（推荐） | O(n² · L) | O(n + Σ|w|) | 简洁直观，面试首选，L 为子串比较成本 |
|
||
| Trie + DP | O(n · maxLen) | O(n + 字典总字符数) | 适合大数据量场景 |
|
||
|
||
> 注：O(n² · L) 中的 L 来自 Go 中 `s[j:i]` 创建新字符串的成本，平均约等于子串长度的一半。实际评测中 n ≤ 300，完全轻松通过。
|
||
|
||
## 代码
|
||
|
||
### Go 语言实现
|
||
|
||
#### 版本一：哈希表 + DP（推荐 ✅）
|
||
|
||
```go
|
||
// wordBreak determines if s can be segmented into a space-separated sequence
|
||
// of one or more dictionary words.
|
||
func wordBreak(s string, wordDict []string) bool {
|
||
// 将字典转为哈希集合，实现 O(1) 子串查找
|
||
ws := make(map[string]bool)
|
||
for _, w := range wordDict {
|
||
ws[w] = true
|
||
}
|
||
|
||
n := len(s)
|
||
|
||
// dp[i] = s[:i] 能否被字典中的词拼接
|
||
dp := make([]bool, n+1)
|
||
|
||
// 边界：空字符串可以被拆分
|
||
dp[0] = true
|
||
|
||
// 自底向上填表
|
||
for i := 1; i <= n; i++ {
|
||
for j := 0; j < i; j++ {
|
||
// 如果前 j 个字符可以拆分，且 s[j:i] 在字典中
|
||
if dp[j] && ws[s[j:i]] {
|
||
dp[i] = true
|
||
break // 找到一个合法拆分就够了
|
||
}
|
||
}
|
||
}
|
||
|
||
return dp[n]
|
||
}
|
||
```
|
||
|
||
> [!summary] 💡 代码结构拆解
|
||
> - **建哈希集合**：O(Σ|w|)，把数组字典转为 O(1) 查找的 map，这一步是整个优化的基石
|
||
> - **外层 for i**：从左到右依次计算 dp[1] 到 dp[n]，确保用到 dp[j] 时它已经被算好了
|
||
> - **内层 for j**：枚举最后一个词的分割点。`dp[j] && ws[s[j:i]]` 双条件：前半截已拆好 + 后半截是合法词汇
|
||
> - **break**：一旦发现一个合法的 j 就让 dp[i]=true 并跳出内层循环——不需要枚举更多了
|
||
|
||
#### 版本二：带最大词长剪枝
|
||
|
||
```go
|
||
// wordBreakWithPruning is an optimized version using the maximum word length
|
||
// to reduce the inner loop range.
|
||
func wordBreakWithPruning(s string, wordDict []string) bool {
|
||
ws := make(map[string]bool)
|
||
maxLen := 0
|
||
for _, w := range wordDict {
|
||
ws[w] = true
|
||
if len(w) > maxLen {
|
||
maxLen = len(w)
|
||
}
|
||
}
|
||
|
||
n := len(s)
|
||
dp := make([]bool, n+1)
|
||
dp[0] = true
|
||
|
||
for i := 1; i <= n; i++ {
|
||
// j 的下限：子串 s[j:i] 的长度不能超过字典中最长单词
|
||
start := i - maxLen
|
||
if start < 0 {
|
||
start = 0
|
||
}
|
||
for j := start; j < i; j++ {
|
||
if dp[j] && ws[s[j:i]] {
|
||
dp[i] = true
|
||
break
|
||
}
|
||
}
|
||
}
|
||
|
||
return dp[n]
|
||
}
|
||
```
|
||
|
||
> [!summary] 💡 两种版本的差异
|
||
> - 版本二的内层循环最多只遍历 maxLen（≤20）次，而非全部 i 次。当 n=300 且 maxLen=20 时，内层次数从 300 降到 20，性能提升约 15 倍
|
||
> - 代码略微复杂，但对本题 n ≤ 300 的限制来说两者都轻松 AC，优先使用版本一
|
||
|
||
### 执行过程演示（s = "leetcode"）
|
||
|
||
```
|
||
wordDict = ["leet", "code"] → 哈希集合: {"leet":true, "code":true}
|
||
n = 8, dp 初始: [T, F, F, F, F, F, F, F, F]
|
||
|
||
i=1: s[0:1]="l"
|
||
j=0: dp[0]&&ws["l"] → T && F → 不更新
|
||
|
||
i=2: s[0:2]="le"
|
||
j=0: dp[0]&&ws["le"] → T && F
|
||
j=1: dp[1]&&ws["e"] → F && ... → 跳过
|
||
|
||
i=3: s[0:3]="lee"
|
||
j=0: dp[0]&&ws["lee"] → T && F
|
||
j=1: dp[1]&&ws["ee"] → F && ... → 跳过
|
||
j=2: dp[2]&&ws["e"] → F && ... → 跳过
|
||
|
||
i=4: s[0:4]="leet" ← 注意！
|
||
j=0: dp[0]&&ws["leet"] → T && T → dp[4]=true ✓! break
|
||
|
||
i=5: s[0:5]="leetc"
|
||
j=0: dp[0]&&ws["leetc"] → T && F
|
||
j=1: dp[1]&&... → F 跳过
|
||
j=2: dp[2]&&... → F 跳过
|
||
j=3: dp[3]&&... → F 跳过
|
||
j=4: dp[4]&&ws["c"] → T && F → 不更新
|
||
|
||
i=6: s[0:6]="leetcod"
|
||
j=4: dp[4]&&ws["cod"] → T && F → 不更新
|
||
（其余 j 对应 dp[j]=F，跳过）
|
||
|
||
i=7: s[0:7]="leetcode"
|
||
j=4: dp[4]&&ws["code"] → T && T → dp[7]=true ✓! break
|
||
|
||
等等——上面是 i=7 子串只有6个字母，修正：
|
||
|
||
i=7: s[0:7]="leetcode" ← 错了，是7个字符 "leetco"
|
||
... 都不匹配 → dp[7]=false
|
||
|
||
i=8: s[0:8]="leetcode"
|
||
j=0: dp[0]&&ws["leetcode"] → T && F
|
||
j=1: dp[1]&&... → F 跳过
|
||
...
|
||
j=4: dp[4]&&ws["code"] → T && T → dp[8]=true ✓! break
|
||
|
||
最终: dp[8] = true ✅
|
||
拆分方式: "leet" + "code"
|
||
```
|
||
|
||
### 复杂度分析
|
||
|
||
- **时间复杂度：O(n² · L)** — 两层循环共 n(n+1)/2 次迭代，每次 substring 切割和哈希查找耗时 O(L)（L 为子串长度）。代入题目约束 n ≤ 300，最坏约 4.5 × 10⁴ 次操作
|
||
- **空间复杂度：O(n + Σ|w|)** — dp 数组占用 O(n)，哈希集合存储字典所有单词占用 O(Σ|w|)
|
||
|
||
> 使用版本二（maxLen 剪枝）后时间复杂度降为 **O(n · maxLen · L)**，即 O(n · maxLen²)，上限约 300 × 20² = 1.2 × 10⁵ 次操作。
|
||
|
||
## 举一反三
|
||
|
||
这道题是 **"线性 DP + 枚举分割点"** 的经典代表，也是理解字符串 DP 的入口题：
|
||
|
||
- [[84-完全平方数]] — 同样是"枚举最后一项做决策"的 DP 模式，只是这里选的是"词"而非"数"
|
||
- [[85-零钱兑换]] — 本质相通：都是给定一组可选元素，判断/求是否能拼出目标。零钱兑换求最小数量，本题只求可行性（布尔版）
|
||
- LeetCode 140. 单词拆分 II —— **变种**：不只返回 true/false，而是返回所有可能的拆分结果，需要回溯枚举
|
||
- LeetCode 464. 我能赢吗 —— 博弈论 + 状态压缩 DP，思想有相似之处
|
||
|
||
> [!summary] 📌 本节要点
|
||
> 1. 定义 dp[i] = s[:i] 能否用字典词拼接
|
||
> 2. 状态转移：dp[i] = OR(dp[j] && s[j:i] ∈ wordDict)，枚举分割点 j
|
||
> 3. 边界 dp[0] = true，初始化其余为 false
|
||
> 4. 用哈希集合将字典查询降到 O(1)，否则退化为 O(n² · m · L)
|
||
> 5. 可优化：maxLen 剪枝让内层循环最多跑 20 次；一旦 dp[n]=true 可提前终止
|
||
> 6. 复杂度 O(n² · L)，n ≤ 300 时非常高效
|