知序
返回
保存草稿
发布
H1
H2
H3
1
2
3
Excalidraw 图
AI 写作
AI 优化
目录
输入内容后显示目录
Markdown
# 11 - 单词拆分 ## 题目(LeetCode 139) 给定字符串 s 和字典 wordDict,判断 s 是否可以被拆分为一个或多个字典中的单词。 ``` 输入:s = "leetcode", wordDict = ["leet", "code"] 输出:true("leet" + "code") 输入:s = "applepenapple", wordDict = ["apple", "pen"] 输出:true("apple" + "pen" + "apple") 输入:s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"] 输出:false ``` ## 大白话理解 在字符串的不同位置切一刀,看看切出来的每一段是不是字典里的单词。 ``` "leetcode" 切法 1:l | eetcode → "l" 不在字典,失败 切法 2:le | etcode → "le" 不在字典,失败 切法 3:lee | tcode → "lee" 不在字典,失败 切法 4:leet | code → "leet" 在字典!再看 "code" 是否能拆分 "code" 整体在字典 → 成功! ``` ## 四步法 ``` 第 1 步:dp[i] = s 的前 i 个字符能否被拆分 dp[i] = true 表示 s[0..i-1] 可以被字典中的单词拼出来 第 2 步:dp[i] = true,当且仅当存在某个 j(0 <= j < i)使得: dp[j] == true(前 j 个字符可以拆分) 且 s[j..i-1] 在字典中(从 j 到 i-1 这段是一个单词) 翻译成人话: "前 i 个字符能拆分" = "存在一个切割点 j,使得前 j 个字符能拆分, 且 j 到 i 这段是一个完整的单词" 第 3 步:dp[0] = true(空字符串可以被拆分,不需要任何单词) 第 4 步:从小到大遍历 i(1 到 n) ``` ### 为什么 dp[0] = true? ``` dp[0] 表示空字符串能否被拆分,答案是 true(什么都不选就行) 这是一个"哨兵"值,让后续的计算能正确处理从头开始的单词: 如果 s[0..i-1] 整体是一个单词,那 j=0 时: dp[0]=true 且 s[0..i-1] 在字典中 → dp[i]=true 如果没有 dp[0]=true,这种情况就处理不了 ``` ## 手动模拟(这是理解的关键) ### 示例 1:s="leetcode", wordDict=["leet","code"] ``` n = 8 dp = [T, F, F, F, F, F, F, F, F] 0 1 2 3 4 5 6 7 8 dp[0] = true(初始化) dp[1]:检查所有 j(0 <= j < 1) j=0: dp[0]=T 且 s[0..0]="l" 在字典?否 dp[1] = false dp[2]:检查所有 j(0 <= j < 2) j=0: dp[0]=T 且 s[0..1]="le" 在字典?否 j=1: dp[1]=F,跳过 dp[2] = false dp[3]:类似,"lee" 不在字典 → dp[3] = false dp[4]:检查所有 j(0 <= j < 4) j=0: dp[0]=T 且 s[0..3]="leet" 在字典?是! dp[4] = true ← "leet" 可以拆分 dp[5]:检查所有 j(0 <= j < 5) j=0: dp[0]=T 且 s[0..4]="leetc" 在字典?否 j=1: dp[1]=F,跳过 j=2: dp[2]=F,跳过 j=3: dp[3]=F,跳过 j=4: dp[4]=T 且 s[4..4]="c" 在字典?否 dp[5] = false dp[6]: j=4: dp[4]=T 且 s[4..5]="co" 在字典?否 其他 j 的 dp[j]=F,跳过 dp[6] = false dp[7]: j=4: dp[4]=T 且 s[4..6]="cod" 在字典?否 dp[7] = false dp[8]: j=0: dp[0]=T 且 s[0..7]="leetcode" 在字典?否 j=4: dp[4]=T 且 s[4..7]="code" 在字典?是! dp[8] = true ← "leet"+"code" 可以拆分 dp = [T, F, F, F, T, F, F, F, T] 答案 = dp[8] = true ✓ ``` ### 示例 2:s="catsandog", wordDict=["cats","dog","sand","and","cat"] ``` n = 9 dp = [T, F, F, F, F, F, F, F, F, F] dp[3]:s[0..2]="cat" 在字典 → dp[3]=true dp[4]:s[0..3]="cats" 在字典 → dp[4]=true dp[7]:j=3: dp[3]=T 且 s[3..6]="sand" 在字典 → dp[7]=true j=4: dp[4]=T 且 s[4..6]="and" 在字典 → dp[7]=true(已经是 true) dp[9]: j=3: dp[3]=T 且 s[3..8]="sandog" 在字典?否 j=4: dp[4]=T 且 s[4..8]="andog" 在字典?否 j=7: dp[7]=T 且 s[7..8]="og" 在字典?否 dp[9] = false 答案 = dp[9] = false ✓ ("catsandog" 无法被字典中的单词拼出来) ``` ## 代码 ```java public boolean wordBreak(String s, List<String> wordDict) { Set<String> dict = new HashSet<>(wordDict); // 用 Set 加速查找 int n = s.length(); boolean[] dp = new boolean[n + 1]; dp[0] = true; for (int i = 1; i <= n; i++) { for (int j = 0; j < i; j++) { if (dp[j] && dict.contains(s.substring(j, i))) { dp[i] = true; break; // 找到一个就够了 } } } return dp[n]; } ``` 时间 O(n² × m),m 是字典中最长单词的长度(substring 操作)。空间 O(n)。 ## 注意:容易困惑的地方 ``` Q:为什么要枚举所有切割点 j,而不是只看最后一个单词? A:因为不知道最后一个单词从哪里开始。 枚举所有 j,就是枚举"最后一个单词"的所有可能起始位置。 Q:dp[j] 为 false 时为什么可以跳过? A:dp[j]=false 说明前 j 个字符无法被拆分, 即使 s[j..i-1] 在字典中,整体也无法拆分,所以跳过。 Q:字典中的单词可以重复使用吗? A:可以!"applepenapple" 中 "apple" 用了两次。 DP 的每个位置都独立判断,不限制单词使用次数。 ``` ## 一句话总结 `dp[i] = 存在 j 使得 dp[j]=true 且 s[j..i-1] 在字典中`。枚举所有切割点,dp[0]=true 是关键的初始值。 --- 上一篇:[10 - 最大子数组和](./10-max-subarray.md) | 下一篇:[12 - 0-1背包](./12-knapsack.md)
预览
发布文章
添加摘要让读者更快了解文章内容
取消
确认发布
AI 写作助手
输入一个主题,AI 将为你生成一篇 Markdown 博客文章
AI 正在写作中...
取消
开始生成
AI 优化助手
描述你的修改需求,AI 将在原文基础上进行补充或微调
AI 正在优化中...
取消
开始优化
画布
从已有图里选
✕
图名
保存后生成 /images/excalidraw/<图名>.svg(只能用字母、数字、短横线、下划线、点)
取消
保存并插入