wonder/leetcode-go

Fork 0

Files

T

wonder 4b961751ca vault backup: 2026-05-17 09:38:35

2026-05-17 09:38:35 +08:00

13 KiB

Raw Permalink Blame History

tags, create time

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 的子串。

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

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
Trie + DP	O(n · maxLen)	O(n + 字典总字符数)	适合大数据量场景

注：O(n² · L) 中的 L 来自 Go 中 s[j:i] 创建新字符串的成本，平均约等于子串长度的一半。实际评测中 n ≤ 300，完全轻松通过。

代码

Go 语言实现

版本一：哈希表 + DP（推荐 ✅）

// 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 并跳出内层循环——不需要枚举更多了

版本二：带最大词长剪枝

// 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] 📌 本节要点

定义 dp[i] = s[:i] 能否用字典词拼接

状态转移：dp[i] = OR(dp[j] && s[j:i] ∈ wordDict)，枚举分割点 j

边界 dp[0] = true，初始化其余为 false

用哈希集合将字典查询降到 O(1)，否则退化为 O(n² · m · L)

可优化：maxLen 剪枝让内层循环最多跑 20 次；一旦 dp[n]=true 可提前终止

复杂度 O(n² · L)，n ≤ 300 时非常高效

13 KiB Raw Permalink Blame History Unescape Escape