LeetCode 139. 单词拆分

◎

本节目标

以可达前缀为状态，判断能否在末尾接上一个字典词。

这是序列与字符串动态规划中布尔前缀可达性的母题。

题意与约束

判断字符串能否被拆成一个或多个字典单词，字典中的单词可重复使用。

第一反应与重复子问题

如果较短前缀已经可拆，且末尾恰好是一个字典词，较长前缀也可拆；同一前缀是否可达会被多个后缀查询。

状态定义与转移推导

令 dp[i] 表示长度为 i 的前缀能否拆分。dp[0] 为真；枚举词 word，若 dp[i-|word|] 为真且末尾匹配该词，就令 dp[i] 为真。

正确性依据

任一完整拆分都有最后一个字典词，去掉它后是可达前缀；反之，在可达前缀后接匹配词必构成合法拆分。

样例执行过程

cars 可先拆为 ca，再接 rs；不能因 car 是前缀就贪心地提前失败。

代码实现

C++

C++17

#include <string>
#include <vector>
using namespace std;

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        vector<bool> reachable(s.size() + 1, false);
        reachable[0] = true;
        for (int end = 1; end <= static_cast<int>(s.size()); end++) {
            for (const string& word : wordDict) {
                int start = end - static_cast<int>(word.size());
                if (start >= 0 && reachable[start] && s.compare(start, word.size(), word) == 0) {
                    reachable[end] = true;
                    break;
                }
            }
        }
        return reachable[s.size()];
    }
};

Python

Python 3

class Solution:
    def wordBreak(self, s: str, wordDict: list[str]) -> bool:
        reachable = [False] * (len(s) + 1)
        reachable[0] = True
        for end in range(1, len(s) + 1):
            for word in wordDict:
                start = end - len(word)
                if start >= 0 and reachable[start] and s[start:end] == word:
                    reachable[end] = True
                    break
        return reachable[-1]

复杂度分析

设字符串长度为 n、字典总字符量为 L，朴素末尾比较的时间约为 O(nL)，状态空间 O(n)。

边界与易错点

• 空前缀必须设为可达，才能匹配开头的单词。
• 不要只按最长或最短单词贪心，后缀可能需要另一种切分。

模式迁移

最少切分数、句子枚举和字符串匹配均可先用前缀可达性过滤无效状态。