#139
中等
低频
动态规划单词拆分
这是一道围绕字符串展开的高频练习。建议先掌握「动态规划」这套写法，再结合下方步骤讲解理解状态维护、边界处理和复杂度取舍。
字符串
题目分析
给你一个字符串 s 和一个单词字典。
要求判断能不能把 s 切分成若干个字典里的单词，并且所有字符都必须刚好被用完。
一句话概括：
判断字符串前缀能不能一步一步被字典中的单词合法拼出来。
接下来怎么看推荐代码： 带着这个理解再看推荐代码时，重点观察这条主线：用一维 DP 判断前缀能否拆分：如果前缀
j 可达，且 s[j:i] 在词典里，那么前缀 i 也可达。推荐代码
推荐解法：动态规划
时间复杂度： O(n^2)
空间复杂度： O(n)
核心思路： 用一维 DP 判断前缀能否拆分：如果前缀
j 可达，且 s[j:i] 在词典里，那么前缀 i 也可达。class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
Set<String> words = new HashSet<>(wordDict);
boolean[] dp = new boolean[s.length() + 1];
dp[0] = true;
for (int i = 1; i <= s.length(); i++) {
for (int j = 0; j < i; j++) {
if (dp[j] && words.contains(s.substring(j, i))) {
dp[i] = true;
break;
}
}
}
return dp[s.length()];
}
}结构化讲解
面试时怎么讲
开场思路
这题我会用一维 DP，把问题转成“每个前缀是否可拆分”。
核心过程
- 先把词典放进哈希集合，便于 O(1) 查片段。
- 定义
dp[i]表示前 i 个字符能否被拆分。 - 枚举最后一次切分点 j，看
dp[j]是否为真且s[j:i]是否在词典里。 - 只要存在一个合法 j，就把
dp[i]设为 true。
复杂度总结
时间复杂度 O(n^2)，空间复杂度 O(n)。
面试补一句：这题不要贪心，核心是前缀可达性。
核心思路
单词拆分的本质是前缀可达性。每个位置只要能找到一个切分点，使左边前缀可拆分、右边这一段又在词典里，就说明当前前缀也能被拆开。
步骤讲解
1
定义前缀可达状态
令 dp[i] 表示前 i 个字符是否可以被词典完全拆分。
为什么这样做：题目问的是整串是否可拆，所以从前缀状态推进最自然。
对应代码提示：boolean[] dp = new boolean[n + 1]; dp[0] = true;
2
枚举切分点
对每个位置 i，尝试所有 j < i 作为最后一次切分点。
为什么这样做：只要存在一个合法切分点，就能证明当前前缀可达。
对应代码提示：for (int j = 0; j < i; j++) { ... }
3
前缀可达且当前片段在词典里就置真
若 dp[j] 为真，且 s.substring(j, i) 在词典集合中，就令 dp[i] = true。
为什么这样做：这正对应“左边已拆好，最后一段也合法”。
对应代码提示：if (dp[j] && words.contains(s.substring(j, i))) dp[i] = true;
易错点
词典用列表线性查找
这样每次检查片段都要额外遍历词典，性能会明显变差。
正确理解：先把词典放进哈希集合。
只从头尝试最长单词贪心切
局部最优切法不一定能让后续前缀可达。
正确理解：这题要看所有可能切分点，不能贪心。
dp[0] 没设成 true
后续所有状态都失去起点，整个 DP 无法启动。
正确理解：空字符串前缀必须视作可拆分。
复杂度与适用判断
时间复杂度：O(n^2)
空间复杂度：O(n)
比其他方案更好在哪里：比 DFS 暴力搜索稳定得多，不会在重复子问题上反复回溯。
适用判断：字符串题里只要出现“能否拆成若干合法片段”，优先考虑前缀 DP。
额外提醒
dp[0] = true是整题启动点。