139. 单词拆分 (Medium)
专题归类： 10-动态规划 LeetCode 链接： https://leetcode.cn/problems/word-break/
在线做题： 写 Python 代码并运行 · Java 跳转 LeetCode
题目描述
给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s。
注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。
示例 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 <= 300
- 1 <= wordDict.length <= 1000
- 1 <= wordDict[i].length <= 20
- s 和 wordDict[i] 仅由小写英文字母组成
题目详细分析
- 数据范围：s 最长 300，字典最多 1000 个单词，单词最长 20。O(n²) 的 DP 可接受。
- 核心约束：单词可以重复使用，顺序要求完全匹配（完全背包的字符串版本）。
- 边界条件：空字符串可以拆分（dp[0] = True）；字典中单词都是小写字母。
- 隐藏条件：拆分的”切割点”是 dp 的关键——如果 s[j:i] 是字典词且 s[0:j] 可拆分，则 s[0:i] 可拆分。
小白版直白理解
你有一堆积木（字典里的单词），想拼成一个指定的长条（字符串 s）。积木可以重复使用，关键是拼接的顺序必须和长条完全一致。你从左边开始拼——先看前 1 个字母能不能用一块积木拼成，前 2 个字母能不能，前 3 个能不能……每多拼一块，就看新多出来的那截字母是否正好是一块积木。这就好比玩拼图，每次在末尾拼上一块。
解题思路
思路一：动态规划（推荐）
核心洞察：定义 dp[i] 表示 s 的前 i 个字符（s[0:i]）能否被拆分。对于每个位置 i，检查是否存在一个切割点 j < i，使得 s[0:j] 可拆分且 s[j:i] 在字典中。这相当于完全背包的”组合”问题——物品能否按顺序拼成目标。
DP 五步法：
- dp 定义：
dp[i]表示 s 的前 i 个字符是否能被拆分成字典中的单词 - 递推公式：
dp[i] = any(dp[j] and s[j:i] in word_set for j in range(i)) - 初始化：
dp[0] = True（空字符串视为可拆分） - 遍历顺序：从 i=1 到 len(s)，内层遍历 j < i
- 举例验证：s=“leetcode”, wordDict=[“leet”,“code”] → dp[0]=T, dp[4]=T（“leet”）, dp[8]=dp[4] and “code” in dict = T ✓
def wordBreak(s, wordDict):
word_set = set(wordDict) # 哈希集，O(1) 查找
n = len(s)
dp = [False] * (n + 1)
dp[0] = True # 空字符串可以拼出
for i in range(1, n + 1):
for j in range(i): # 枚举切割点
if dp[j] and s[j:i] in word_set:
dp[i] = True
break # 找到即可退出
return dp[n]思路二：BFS / 单词接龙
将字符串索引视为节点，从 0 出发，每次”接上”一个字典中的单词跳到一个新位置，看能否到达 n。
from collections import deque
def wordBreak(s, wordDict):
word_set = set(wordDict)
n = len(s)
queue = deque([0])
visited = [False] * (n + 1)
visited[0] = True
while queue:
start = queue.popleft()
if start == n:
return True
for end in range(start + 1, n + 1):
if not visited[end] and s[start:end] in word_set:
visited[end] = True
queue.append(end)
return False思路三：Trie 树优化（字典很大时）
如果字典特别大但单词较短，用 Trie 树优化子串查找。
class TrieNode:
def __init__(self):
self.children = {}
self.is_word = False
def wordBreak(s, wordDict):
# 构建 Trie
root = TrieNode()
for word in wordDict:
node = root
for ch in word:
if ch not in node.children:
node.children[ch] = TrieNode()
node = node.children[ch]
node.is_word = True
n = len(s)
dp = [False] * (n + 1)
dp[0] = True
for i in range(n):
if dp[i]:
node = root
for j in range(i, n):
if s[j] not in node.children:
break
node = node.children[s[j]]
if node.is_word:
dp[j + 1] = True
return dp[n]易错点
- dp 索引偏移：
dp[i]对应 s[0:i]（前 i 个字符，不包含 s[i]），所以dp[n]是最终答案。 - skipping break：找到解后及时
break内层循环，避免多余计算。 - 子串截取性能：
s[j:i]是 O(k) 操作。字典用 set 保证 O(1) 查找。如果 n 很大可考虑用 Trie 树优化。 - 字典去重：dict 中可能有重复单词，用 set 去重可以优化，但不是必须。
框架提炼
完全背包（字符串拼接 / 顺序敏感）模板：
def string_break(s, word_set):
n = len(s)
dp = [False] * (n + 1)
dp[0] = True
for i in range(1, n + 1): # 遍历背包（字符串长度）
for j in range(i): # 枚举切割点
if dp[j] and s[j:i] in word_set:
dp[i] = True
break
return dp[n]与硬币找零的区别：这里物品有”顺序”要求（必须按字符顺序拼接），所以两层循环不能交换。
关联题目
- 322-零钱兑换 — 完全背包求最少数量，dp 类型不同但结构相似
- 300-最长递增子序列 — 子序列 DP，同样需要枚举所有 j < i
- 140-单词拆分 II — 本题进阶版，要求输出所有拆分结果（DFS + 回溯）