单词拆分 图解题解

单词拆分在判定什么

给字符串 s 和词典 wordDict，问能否把 s 从头到尾切成若干段，使每一段都恰好是词典里的词，词可以重复使用，答案只要 true 或 false。比如 s = "leetcode"、词典含 "leet" 和 "code"，切成 leet + code 即为 true。注意必须整串切干净，多一个字符盖不住都算失败，也不允许段与段重叠或留缝。

为什么不能贪心地每次匹配最长的词

直觉做法是从左往右扫，每次贪心咬下能匹配的最长词。反例很快出现：s = "aaaa"，词典是 ["aaa", "a"]，贪心先咬 "aaa"，剩下一个 "a" 能配上纯属侥幸；换成 s 长度稍变或词典稍变，先咬最长就把后面卡死，而 a + a + a + a 这样的切法明明存在。前面的选择会影响后面能不能切，单向贪心看不见这种牵连。

改成回溯搜索所有切法，最坏是指数级分支。但仔细看会发现大量重复：不同的前段切法常常在同一个位置会师，之后「剩下这一截能不能切」是同一个子问题，被反复求解。子问题只由「切到了哪个位置」决定——这就是重叠子问题加无后效性，动态规划的标准入口。

dp[i] 的含义与 dp[0] 为什么是 true

定义 dp[i] 为「s 的前 i 个字符（即 s[0:i]）能否被词典完整切分」，i 从 0 到 n，最终答案是 dp[n]。下标是「长度」而非「字符位置」，好处是空前缀有了名分：dp[0] = true，表示空串用零个词就拼成了。它不是凑数的技巧，而是第一个词的转移依据——切下开头的 "leet" 时，靠的正是「它左边的空串已经合法」。漏设 dp[0]，整张表推不起来，全盘皆否。

枚举最后一个词的转移为什么完备

算 dp[i] 时，盯住一种切法里的最后一个词：它必然从某个位置 j 开始、到 i 结束。于是「前 i 个字符可切」等价于「存在切点 j，使前 j 个字符可切，且 s[j:i] 恰好是词典里的词」。j 从 0 到 i-1 全枚举，任何合法切法的最后一刀都会被扫到，不存在漏判；找到一个成立的 j 就可以 break，因为 dp[i] 只关心存在性。

两个条件缺一不可：只查 s[j:i] 成词而不查 dp[j]，就可能接在一段根本切不开的前缀后面，链条中间是断的。把词典先存进哈希集合，s[j:i] in words 的判断均摊 O(1) 次哈希、代价主要在取子串本身。

复杂度多少，还能怎么提速

外层 i、内层 j 共约 n²/2 对切点，每对要取子串并做哈希，长度记 L，总时间约 O(n² × L)；dp 数组长 n + 1 加一个词典集合，空间 O(n) 级别。

提速有两条常用路：一是先算出词典里的最大词长 maxLen，内层 j 只需回看 i - maxLen 以内的范围，比它更早的切点不可能成词；二是把词典建成 Trie 前缀树，沿字符逐个下走做匹配，省掉反复取子串。若题目升级为列出所有具体拆分方案，那是 LeetCode 140 单词拆分 II，要用记忆化搜索去枚举句子，判定版的 dp 思路是它的地基。

Python

def wordBreak(s, wordDict):
    words = set(wordDict)
    n = len(s)
    dp = [False] * (n + 1)
    dp[0] = True
    for i in range(1, n + 1):
        for j in range(i):
            if dp[j] and s[j:i] in words:
                dp[i] = True
                break
    return dp[n]

C++

bool wordBreak(string s, vector<string>& wordDict){
    unordered_set<string> words(wordDict.begin(), wordDict.end());
    int n = s.size();
    vector<bool> dp(n + 1, false);
    dp[0] = true;
    for(int i = 1; i <= n; ++i)
        for(int j = 0; j < i; ++j)
            if(dp[j] && words.count(s.substr(j, i - j))){
                dp[i] = true; break;
            }
    return dp[n];
}

Java

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++)
            if(dp[j] && words.contains(s.substring(j, i))){
                dp[i] = true; break;
            }
    return dp[n];
}