vvrf / DSA.log

问题拆解

给一个字符串和一本词典，问字符串能否被切分成若干个词典里的单词（可重复使用）。直觉的做法是贪心匹配：从头开始，遇到词典里的词就切一刀。但反例很容易造——s = "aaab"，词典 {"a", "aaa"}，先切 "aaa" 就把 "a" + "a" + "ab" 之外唯一可能的方案堵死了。切分点的选择会互相影响，需要把所有可能都留住。

纯递归地枚举每一刀又会超时，因为不同的切法会反复问同一个问题：“剩下这段后缀能不能拆？”重叠子问题出现，就轮到 DP 登场。设 dp[i] 表示前 i 个字符（即 s[0..i)）能否被拆分。老规矩看最后一步：如果能拆，最后一个单词总得从某个位置 j 开始，那么需要 dp[j] 为真，且 s[j..i) 在词典里。任何一个 j 满足即可。

状态只记“能不能”，不记“怎么拆”——把指数级的切分方案压缩成 n+1 个布尔值，正是 DP 消除重复计算的方式。

布尔 DP 加哈希集合查词

词典先放进哈希集合，s[j..i) 是否为单词就是一次 O(1) 查询（忽略子串哈希的长度因素）。

public boolean wordBreak(String s, List<String> wordDict) {
    Set<String> words = new HashSet<>(wordDict);
    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++) { // 最后一个单词是 s[j..i)
            if (dp[j] && words.contains(s.substring(j, i))) {
                dp[i] = true;
                break;
            }
        }
    }
    return dp[n];
}

def wordBreak(s: str, wordDict: List[str]) -> bool:
    words = set(wordDict)
    n = len(s)
    dp = [True] + [False] * n  # dp[0]：空串可拆
    for i in range(1, n + 1):
        for j in range(i):  # 最后一个单词是 s[j:i]
            if dp[j] and s[j:i] in words:
                dp[i] = True
                break
    return dp[n]

func wordBreak(s string, wordDict []string) bool {
    words := make(map[string]bool, len(wordDict))
    for _, w := range wordDict {
        words[w] = true
    }
    n := len(s)
    dp := make([]bool, n+1)
    dp[0] = true // 空串可拆
    for i := 1; i <= n; i++ {
        for j := 0; j < i; j++ { // 最后一个单词是 s[j:i]
            if dp[j] && words[s[j:i]] {
                dp[i] = true
                break
            }
        }
    }
    return dp[n]
}

pub fn word_break(s: String, word_dict: Vec<String>) -> bool {
    let words: std::collections::HashSet<&str> = word_dict.iter().map(|w| w.as_str()).collect();
    let n = s.len();
    let mut dp = vec![false; n + 1];
    dp[0] = true; // 空串可拆
    for i in 1..=n {
        for j in 0..i {
            // 最后一个单词是 s[j..i]
            if dp[j] && words.contains(&s[j..i]) {
                dp[i] = true;
                break;
            }
        }
    }
    dp[n]
}

dp[0] = true 是整个递推的种子：它表示空串“已拆完”，让第一个单词（j = 0 的情形）有真值可以接。漏掉它，整个数组永远全假。找到一个可行的 j 就 break，因为 dp[i] 只需要“存在”，继续枚举是白费功夫。还可以做一个小剪枝：先算出词典里最长单词的长度 L，内层 j 只需从 i - L 开始枚举——单词不可能比 L 更长。

复杂度

指标	复杂度	原因
时间	`O(n^2)`	双重循环，子串构造与哈希查询计入常数或再乘长度因子
空间	`O(n + m)`	dp 数组加词典集合（m 为词典总字符数）

可以迁移的模式

字符串切分问题的通用状态：dp[i] 描述前缀 s[0..i)，转移枚举最后一段的起点；
可行性 DP 只存布尔值，找到一个真分支就 break；要输出方案时再把“从哪转移来”记下来回溯；
集合查询（哈希集合、Trie）负责“这一段是不是合法单元”，和 DP 的骨架解耦。

同样的骨架把“或”换成“计数”“最小代价”，就得到单词拆分 II、完全平方数这一族题——前缀状态 + 枚举最后一段，是字符串 DP 的第一反应。