单词拆分如何用动态规划判断字符串能否由词典组成？

简化版

单词拆分用 dp[i] 表示 s[0..i-1] 能否被词典拆分。枚举切分点 j，如果 dp[j] 为真且 s[j..i-1] 在词典中，则 dp[i]=true。

详细版

这题的最后一步一定是某个词典单词作为后缀。设最后一个单词是 s[j:i]，那么前缀 s[0:j] 必须也能被拆分，所以状态转移是 dp[i] = any(dp[j] && dict.contains(s.substring(j,i)))。初始化 dp[0]=true，表示空前缀可作为拼接起点。

优化点是限制后缀长度：如果词典最长单词长度为 maxLen，枚举 j 时只需要看 i - maxLen 到 i 的范围。复杂度通常是 O(n^2) 次切分判断，具体还受 substring 成本影响。

完整版教学

一、把问题看成“最后一个单词是谁”

例如：

s = "leetcode"
dict = ["leet", "code"]

如果最后一个单词是 "code"，那么前面的 "leet" 必须也能拆分。动态规划的关键就是枚举最后一个单词的起点。

leet | code
前缀可拆 + 后缀在词典

二、状态定义和初始化

定义 dp[i] 表示前 i 个字符 s[0..i-1] 是否能拆分。

状态	含义
`dp[0]`	空前缀可拆，作为起点
`dp[4]`	`s[0..3]` 是否可拆
`dp[n]`	整个字符串是否可拆

dp[0]=true 是必要的，因为当 s[0:i] 本身就是词典单词时，需要 dp[0] 支持它成立。

记忆钩子：前缀 DP 的空前缀通常是真，它代表“还没开始也算可连接”。

三、状态转移如何推导

如果 s[0:i] 能拆分，最后一个词一定是某段 s[j:i]。于是：

dp[i] = 存在 j，使得 dp[j] == true 且 s[j:i] 在词典中

这个转移把一个全局判断拆成“前缀已可拆”和“最后一段是合法单词”两个条件。

四、用样例走一遍

以 "leetcode" 为例：

i	前缀	可行切分	dp[i]
0	空	起点	true
4	leet	`dp[0] && "leet"`	true
8	leetcode	`dp[4] && "code"`	true

如果输入是 "catsandog"，词典有 "cats","dog","sand","and","cat"，走到后缀 "og" 时没有合法拆分，最终 dp[n]=false。

五、代码模板

boolean wordBreak(String s, List<String> wordDict) {
    Set<String> dict = new HashSet<>(wordDict);
    int maxLen = 0;
    for (String w : wordDict) maxLen = Math.max(maxLen, w.length());

    boolean[] dp = new boolean[s.length() + 1];
    dp[0] = true;
    for (int i = 1; i <= s.length(); i++) {
        for (int j = Math.max(0, i - maxLen); j < i; j++) {
            if (dp[j] && dict.contains(s.substring(j, i))) {
                dp[i] = true;
                break;
            }
        }
    }
    return dp[s.length()];
}

使用 HashSet 是为了让词典查询接近 O(1)。若语言的 substring 会复制字符，还要把 substring 成本也考虑进复杂度。

六、和回溯枚举所有句子的区别

题目	目标	状态返回
单词拆分 I	是否存在拆分	boolean
单词拆分 II	返回所有拆分句子	`List<String>`

单词拆分 I 可以用布尔 DP 提前终止；单词拆分 II 必须枚举所有答案，常用记忆化搜索缓存每个后缀的句子列表。

七、常见误区与追问

误区：只要每个字符出现在某个单词中就可拆。 拆分要求连续子串组成词典单词，不是字符覆盖。
误区：忘记 dp[0]=true。 整个前缀本身是单词时会无法成立。
误区：找到一个词典单词后不检查前缀。 后缀合法还不够，前缀也必须可拆。
追问：为什么可以限制最大单词长度？ 最后一个词长度不可能超过词典最长词。
追问：复杂度是多少？ 基础写法约 O(n^2) 次判断，substring 成本视语言实现而定。
追问：如何返回具体路径？ 用 DFS + memo 返回后缀所有句子，或者 DP 记录前驱切分点再回溯。

八、加强记忆

单词拆分要抓住“最后一个单词”这个视角：dp[i] 看前 i 个字符能否拆，枚举切点 j，只要 dp[j] 已经成立并且 s[j:i] 在词典中，当前前缀就成立。空前缀为真是拼接起点，HashSet 是查询优化，最大词长是循环剪枝。把它和单词拆分 II 的“返回所有句子”区分开，就能回答从存在性到枚举方案的追问。

简化版

详细版