LeetCode Word Break：動態規劃 + 遞歸備忘錄

遞歸 + 備忘錄實現

自頂向下遞歸，dfs(pos) 返回 s[pos..] 能否拆分。用 memo[pos] 記錄結果（-1 未計算，0 false，1 true）。

class Solution {
    vector memo;
    unordered_set dict;
    int maxLen = 0;
public:
    bool wordBreak(string s, vector& wordDict) {
        dict = unordered_set(wordDict.begin(), wordDict.end());
        for (auto& w : wordDict) maxLen = max(maxLen, (int)w.size());
        memo.assign(s.size(), -1);
        return dfs(s, 0);
    }
    bool dfs(const string& s, int pos) {
        if (pos == s.size()) return true;
        if (memo[pos] != -1) return memo[pos];
        for (int len=1; len<=maxLen && pos+len<=s.size(); ++len) {
            if (dict.count(s.substr(pos, len)) && dfs(s, pos+len))
                return memo[pos] = 1;
        }
        return memo[pos] = 0;
    }
};

優化技巧

1. 預計算詞典最大長度 maxLen，限制內層循環上界
2. substr 會拷貝字符串，C++17 可用 string_view 避免拷貝
3. 迭代 DP 避免遞歸棧溢出：for(i=1..n) for(j=max(0,i-maxLen)..i-1) dp[i] |= dp[j] && dict.count(s.substr(j,i-j))

複雜度

• 時間：O(n × maxLen) （查詞典 O(1) 平均）
• 空間：O(n + 總詞典長)

關鍵點

• 「能否拆分」是典型的區間 DP / 線性 DP 問題
• 遞歸 + 備忘錄 等價於自底向上 DP，但代碼更直觀
• maxLen 優化對長字符串、大詞典至關重要

此題是字符串 DP 入門經典，掌握「前綴可行性」狀態定義與轉移邏輯，可解決大量字符串分割/匹配問題。