单词拆分
Word Break
给定字符串和单词字典，判断能否把字符串切成若干个字典中的单词（单词可重复使用）。
在力扣中练习题目描述
给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。
注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。
示例 1：
输入: s = "leetcode", wordDict = ["leet", "code"] 输出: true 解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。
示例 2：
输入: s = "applepenapple", wordDict = ["apple", "pen"] 输出: true 解释: 返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。 注意，你可以重复使用字典中的单词。
示例 3：
输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"] 输出: false
提示：
1 <= s.length <= 3001 <= wordDict.length <= 10001 <= wordDict[i].length <= 20s和wordDict[i]仅由小写英文字母组成wordDict中的所有字符串 互不相同
解题思路
一维 DP · 枚举切分点
dp[i] 只关心前 i 个字符能不能拆完
暴力做法是枚举所有切分位置：n 个字符之间有 n-1 个空隙，每个都可以切或不切，共 2^(n-1) 种，指数级。
但判断“前 i 个字符能不能拆完”并不需要记住具体怎么拆。只要存在一个切分点 j，使得前 j 个字符能拆完，并且 s[j..i) 正好是字典里的单词，那么前 i 个字符就能拆完：
dp[i] = 存在 j < i：dp[j] 为真 且 s[j..i) 在字典中
自拟主例 s = "abcabc"，字典含 a / ab / abc / bc。前 3 个字符既可由 abc 拆出，也可由 a + bc 得到；到第 6 个字符时，abc 接在 3 后面、bc 接在 4 后面，两条路都通。
前 1 个字符："a" 都能接到一个可切分的前缀，dp[1] = T。
- i
- 1
- dp[i]
- T
dp[i] 表示 s 的前 i 个字符能否被拆成字典中的单词；s = "abcabc"
dp[0] = TT✓写入T
dp[1]=dp[0] && "a"T && true=Tdp[0] = true 是空串的初值，也是“从开头切第一个单词”的入口。按 i 从小到大枚举，所有 dp[j]（j < i）都已经确定，不需要回溯具体的切分方案。
前 5 个字符："ab" 都能接到一个可切分的前缀，dp[5] = T。
- i
- 5
- dp[i]
- T
dp[i] 表示 s 的前 i 个字符能否被拆成字典中的单词；s = "abcabc"
dp[3] = TT✓写入T
dp[5]=dp[3] && "ab"T && true=T时间复杂度 O(n²·L)（L 为单词长度，主要花在取子串和哈希），空间 O(n)。
易错点
- dp[0] 设为 false：所有从开头切出的第一个单词都无法成立，整张表全假。
- 子串区间写成 s.substr(j, i) 而不是 s.substr(j, i - j)，长度多算了。
- 只判断“最后一个单词在字典里”而忘了前面的前缀也要可拆，dp[j] 的条件不能省。
BFS · 可达切分点
从下标 0 出发，能切出的每个结尾都是一个新节点
时间同为 O(n²·L)，BFS 把切分点当成图上的点，适合只问“能不能到达”；主解法 DP 更短，也不依赖队列。
把字符串的每个下标看成一个点：如果从 start 能切出一个字典单词到 end，就连一条 start → end 的边。问题变成“0 能否走到 n”。
BFS 从 0 开始，每次尝试所有可能的结尾 end，把能切出的 end 入队。每个点只入队一次，第一次到达 n 就可以返回 true。
它和 DP 的区别只是推进方式：DP 按 i 递增检查所有 j，BFS 按可达顺序扩展。空间都是 O(n)，BFS 还多一个队列。
- 1seen[0] = true，0 入队。
- 2弹出 start，若 start == n 返回 true。
- 3枚举 end，若 s[start..end) 在字典且未访问，标记并入队。
- 4队列空仍未到 n，返回 false。
易错点
- 在出队时才标记 visited：同一个 end 可能被多个 start 重复入队。
- 字典里出现空串：end 从 start+1 开始，避免原地打转。
代码与演示
主解法配有图解；对照解法用于比较思路、复杂度或实现方式。
s = "abcabc", wordDict = ["a","ab","abc","bc"]dp[0] = T：空串不需要切分，是唯一初值。
- s
- abcabc
dp[i] 表示 s 的前 i 个字符能否被拆成字典中的单词；s = "abcabc"
dp[0]=T查看 C++ 代码
延伸阅读
- 如果要求输出所有切分方案（140. 单词拆分 II），就不能只存布尔值，需要记录每个位置的前驱并做回溯。
- 字典用哈希集合而不是线性查找，是这类题能把 O(n²·L) 控制住的关键。