LeetCode 139 Word Break：動態規劃字串分割完整解析

LeetCode 139 經典動態規劃題目：給定字串 s 和單詞字典 dict，判斷 s 是否可分割為字典單詞序列。

問題範例

s = "leetcode"
dict = ["leet", "code"]
返回 true ("leet code")

動態規劃狀態定義

• dp[i]：前綴 s[0...i] (含 i) 是否可分割
• 目標：dp[n-1] (n = s.length)

狀態轉移方程

dp[i] = true, 如果存在 j ∈ [0, i] 使得：
  1. dp[j-1] == true (或 j == 0)
  2. s[j...i] 在字典中

C++ 參考實作 (優化版)

class Solution {
public:
    bool wordBreak(string s, unordered_set& wordDict) {
        int n = s.size();
        vector dp(n, false);
        
        for (int i = 0; i < n; ++i) {
            // 從 i 向前嘗試，發現可行即中斷 (減少遍歷)
            for (int j = i; j >= 0; --j) {
                bool prevOk = (j == 0) || dp[j - 1];
                if (prevOk && wordDict.count(s.substr(j, i - j + 1))) {
                    dp[i] = true;
                    break;  // 關鍵優化：找到一種分割即可
                }
            }
        }
        return dp[n - 1];
    }
};

執行流程圖解

s = "leetcode", dict = {"leet", "code"}

i=0: "l"     → 不在字典
i=1: "le"    → 不在字典
i=2: "lee"   → 不在字典
i=3: "leet"  → 在字典! dp[3]=true
i=4: "e"     → dp[3]=true 但 "e" 不在字典
i=5: "co"    → 不在字典
i=6: "cod"   → 不在字典
i=7: "code"  → 在字典! dp[3]=true 且 "code"在字典 → dp[7]=true
返回 dp[7] = true

複雜度分析

關鍵優化點

1. 倒序內層迴圈：j = i ... 0，長單詞優先匹配，提早命中
2. 提前中斷：break 避免不必要檢查
3. unordered_set O(1) 查找：字典預處理為雜湊表
4. 引用傳遞：string& 避免拷貝

常見變體

• 輸出所有可能分割方案 (DFS + DP 剪枝)
• 最少分割次數 (DP 存儲最小值)
• 單詞可重複使用 / 僅用一次
• 大字典優化：Trie 樹替代 unordered_set

遞歸 + 備忘錄替代方案

bool wordBreak(string s, unordered_set& dict) {
    vector memo(s.size(), -1);  // -1:未計算, 0:false, 1:true
    function dfs = [&](int start) {
        if (start == s.size()) return true;
        if (memo[start] != -1) return memo[start];
        for (int end = start + 1; end <= s.size(); ++end) {
            if (dict.count(s.substr(start, end - start)) && dfs(end))
                return memo[start] = 1;
        }
        return memo[start] = 0;
    };
    return dfs(0);
}