LeetCode Word Break 解題詳解：動態規劃 + 記憶化遞歸優化

問題描述

給定字符串 s 和單詞字典 dict，判斷 s 能否拆分為字典單詞序列。例如 s="leetcode", dict=["leet","code"] → true。

遞歸 + 記憶化（自頂向下）

函數 canBreak(start) 判斷 s[start:] 能否拆分。嘗試所有 end ∈ [start+1, n]，若 s[start:end] ∈ dict 且 canBreak(end) 為真則返回真。用 memo 記錄失敗的 start 避免重複計算。

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);
}

動態規劃（自底向上）

dp[i] = s[0:i] 能否拆分。dp[0]=true。對每個 i，檢查 j < i 使 dp[j] && dict.count(s.substr(j, i-j))。

bool wordBreak(string s, unordered_set& dict) {
    int n = s.size();
    vector dp(n+1, false);
    dp[0] = true;
    for (int i=1; i<=n; ++i)
        for (int j=0; j

優化：Trie 字典 + 最大單詞長度剪枝

將字典構建為 Trie，遍歷 s 時沿 Trie 走，遇到終結標記即找到單詞，避免 substr 開銷。
記錄字典中最大單詞長度 maxLen，內層循環 j ≥ i - maxLen。


複雜度

DP：時間 O(n^2)（含 substr 複製），空間 O(n)。
Trie 優化後：時間 O(n * maxLen)，空間 O(字典總長度)。