LeetCode 139：單詞拆分——動態規劃判斷字符串能否由字典單詞組成

題目描述

給定字符串 s 和單詞字典 wordDict，判斷 s 能否被空格拆分為字典中的單詞序列。單詞可重複使用。

DP 狀態定義

dp[i] 表示 s[0..i-1]（前 i 字符）可拆分。dp[0] = true（空串可拆分）。

狀態轉移

對於每個 i (1..n)，枚舉分割點 j (0..i-1)：

if (dp[j] && wordDict.count(s.substr(j, i-j))) dp[i] = true;

若存在某 j 使前綴可拆分且後綴在字典中，則 dp[i]=true。

C++ 實現

class Solution {
public:
    bool wordBreak(string s, unordered_set<string>& wordDict) {
        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] && wordDict.count(s.substr(j, i-j))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[n];
    }
};

優化：限制最大單詞長度

int maxLen = 0;
for (auto& w : wordDict) maxLen = max(maxLen, (int)w.size());
for (int i = 1; i <= n; ++i)
    for (int j = max(0, i-maxLen); j < i; ++j)  // 只檢查長度 ≤ maxLen 的後綴
        ...

複雜度

• 時間：O(n²)（或 O(n * maxLen)）。
• 空間：O(n)。

總結

單詞拆分是區間型 DP 的典型應用。關鍵在於定義 dp[i] 為「前綴可拆分」，轉移時枚舉最後一個單詞的起始位置。掌握此模板可解決「字符串分割/組合」系列問題。