从能算到秒杀：单词拆分与「能否拼出来」的判定艺术
如果说完全平方数 是在算「最少几个数」，
零钱兑换 是在算「最少几枚硬币」，
那139. 单词拆分 就是在考你：
一个字符串，到底能不能被“拼”出来？
这也是我第一次意识到：
很多 DP 题，其实是在做布尔判断，而不是计数。
🟢 题目速览
LeetCode 139. 单词拆分（中等）
给你一个字符串s和一个字符串列表wordDict。
请你判断：s是否可以被拆分成若干个字典中出现的单词。
✅ 字典中的单词可以重复使用
✅ 不需要用完所有单词
❌ 单词拆分必须恰好覆盖整个字符串
示例
输入：s = "leetcode", wordDict = ["leet","code"] 输出：true 解释：leet + code = leetcode输入：s = "applepenapple", wordDict = ["apple","pen"] 输出：true输入：s = "catsandog", wordDict = ["cats","dog","sand","and","cat"] 输出：false🧠 我的第一反应（很真实）
看到题的第一眼：
回溯？
DFS？
暴力枚举？
直觉告诉我：
只要前面拆对了，后面就能接着拆
于是脑子里立刻出现一句话：
这是 DP。
🚀 解法一：DP（面试唯一正解）
状态定义
dp[i] = s 的前 i 个字符是否可以被成功拆分状态转移
dp[i] = true 当且仅当存在 j < i， 使得 dp[j] == true 且 s[j:i] 在字典中代码（面试必写 ✅）
class Solution { public boolean wordBreak(String s, List<String> wordDict) { Set<String> set = 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] && set.contains(s.substring(j, i))) { dp[i] = true; break; } } } return dp[s.length()]; } }复杂度
指标 | 结果 |
|---|---|
时间复杂度 | O(n²) |
空间复杂度 | O(n) |
✅ 稳定
✅ 好写
✅ 面试安全
🚀 解法二：BFS（理解最短路径思想）
可以把字符串想象成一张图：
节点：字符串下标
边：从一个位置跳到一个能匹配单词的位置
目标：从
0 → n
👉 本质还是可达性问题
（面试中一般不写，但可以用来解释思路）
🎯 我学到的东西
这题最大的收获是：
类型 | 核心 |
|---|---|
完全平方数 | 最少数量 |
零钱兑换 | 最小代价 |
单词拆分 | 可行性判断 |
不是所有 DP 都要算最小值，有时候只关心 true / false。
⚠️ 易错点总结
误区 | 正确做法 |
|---|---|
上来就 DFS | 用 DP 去重 |
忘记 dp[0] | dp[0] = true |
不用 HashSet | 会 TLE |
拆分子串乱拆 | 固定前后边界 |
🧩 一句话总结
单词拆分 = 字符串上的完全背包 = 布尔型 DP
🎤 面试收尾（建议直接背）
“这道题本质是动态规划。
我用
dp[i]表示前 i 个字符是否可以拆分，然后枚举所有可能的切分点，只要前面能拆，后面也在字典里，就成立。
时间复杂度是 O(n²)，空间复杂度是 O(n)。
实际工程中也可以用 Trie 或 BFS 优化。”