单词拆分 · 每个位置 i 都在找合法切口 j

序列 DP · 切刀扫描

判断字符串能否被词典中的单词完整拼出来，单词可以重复使用。核心直觉：对每个右边界 i，往左扫描切分点 j，左边必须已可拆，右边必须是词典单词。

当前输入

s"leetcode"

wordDict["leet", "code"]

leet + code 连续覆盖整串 → dp[8] = true

dp[n]

true

可以完整拆分

复杂度（与代码一致 · maxLen 优化版）

时间

基础面试口径：O(n²)
计入 substring 成本：可能接近 O(n³)
maxLen 优化：O(n · maxLen)

空间

O(n) — dp[0..n] 布尔数组

两个测试用例 · 成功 vs 失败

① 题目

完整拼出 vs 局部匹配

② 定义与初始化

dp[i] 含义 + dp[0]=true

③ 切刀扫描

固定 i，j 左移找合法切口

④ 结论

返回 dp[n]

Step 1/19 · 题目

题目 · 能否被词典单词完整拼出

当前发生了什么

题目 · 能否被词典单词完整拼出

给定字符串 s 和词典 wordDict，判断 s 能否被拆成若干词典单词首尾相接拼出。单词可重复使用，但必须连续覆盖从起点到终点的每一个字符。

机器状态

i (右边界): —
j (切分点): —
子串 s[j:i]: —
dp[j]: —
在词典: —
maxLen: 4

为什么这一步是对的

这不是「字符串里出现了一些词典单词就行」，而是必须从 s[0] 到 s[n-1] 无空隙、无重叠地铺满。

面试该怎么说 · 开题一句话：判断字符串能否被词典中的单词完整拼出来，单词可以重复使用。

切刀扫描台 · i = 右边界 · j = 切分点

idx012345678

sleetcode| n=8

dp 表

dp[i] = s[0:i] 能否被词典单词拼出 · 答案 = dp[8]

Go 代码

题目

1func wordBreak(s string, wordDict []string) bool {
2    wordSet := make(map[string]bool)
3    maxLen := 0
4    for _, word := range wordDict {
5        wordSet[word] = true
6        if len(word) > maxLen {
7            maxLen = len(word)
8        }
9    }
10    n := len(s)
11    dp := make([]bool, n+1)
12    dp[0] = true                    // 空前缀是合法起点
13    for i := 1; i <= n; i++ {
14        for j := i - 1; j >= 0 && i-j <= maxLen; j-- {
15            if dp[j] && wordSet[s[j:i]] {
16                dp[i] = true
17                break               // 找到一个合法切口即可
18            }
19        }
20    }
21    return dp[n]
22}

本步不变量

尚未建立 dp 表，只是把输入摆好。

剧本时间线 · 共 19 步

为什么 dp[0] = true？

dp[0] = true 不是说空字符串就是最终答案。它表示「空前缀是一个合法起点」。

如果没有 dp[0] = true，像 "leet" 这种从下标 0 开始的单词，就无法让 dp[4] 变成 true。

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

当 i = 4, j = 0：dp[0] = true，s[0:4] = "leet" 在词典 → dp[4] = true

页面讲解结构

1. 题目一句话
判断字符串能否被词典中的单词完整拼出来，单词可以重复使用。
2. 核心直觉
每个位置 i 都在找一个合法切口 j。
3. 状态定义
dp[i] = s[0:i] 是否可以被词典单词拼出来
4. 初始化
dp[0] = true — 空前缀是合法起点（见上方说明块）
5. 状态转移
若存在 j 使 dp[j] == true 且 s[j:i] ∈ wordSet，则 dp[i] = true
6. 成功案例
s = "leetcode", wordDict = ["leet", "code"]
7. 失败案例
s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"] — 局部能匹配，无法铺满
8. Go 代码
wordSet + maxLen 优化版（见右侧代码面板）
9. 复杂度
时间 O(n·maxLen)（基础 O(n²)）；空间 O(n) 因 dp[0..n]

面试 · 一段话讲清楚

定义 dp[i] 表示前 i 个字符 s[0:i] 是否可以由词典里的单词拼出来。初始化 dp[0] = true，表示空前缀是一个合法起点。然后枚举右边界 i，再枚举切分点 j。如果 dp[j] 为 true，并且 s[j:i] 在词典中，说明前 i 个字符可以拆分，因此 dp[i] = true。最后返回 dp[n]。为了提高查询效率，先把 wordDict 转成 set；如果要进一步优化，可以只枚举不超过最长单词长度的切分范围。

常见误区

✗ 复杂度写成 O(n) / O(1) —— dp 数组长度 n+1，内层枚举切分点，正确口径是 O(n²) 或 O(n·maxLen)。
✗ 以为「串里出现了词典单词就行」—— 必须从起点到终点连续覆盖，catsandog 就是反例。
✗ 忘记 dp[0] = true —— 从下标 0 切第一刀时左边没有合法 dp[j]。
✗ 找到合法 j 后不 break —— 找到一个切口就足够，不必继续枚举。