从能算到秒杀：单词拆分与「能否拼出来」的判定艺术

如果说完全平方数​ 是在算「最少几个数」零钱兑换​ 是在算「最少几枚硬币」那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, ListString wordDict) { SetString 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 优化。”