LeetCode Decode Ways 解碼方法：動態規劃 O(1) 空間優化解法

LeetCode 91. Decode Ways 詳細題解

給定一個只包含數字的非空字符串，根據映射規則 'A'→1, 'B'→2, ..., 'Z'→26，計算解碼方法總數。例如 "12" 可解碼為 "AB"(1,2) 或 "L"(12)，共 2 種方式。

動態規劃狀態定義

設 dp[i] 表示前 i 個字符的解碼方法數。遞推關係取決於第 i 個字符單獨解碼、或與前一字符組合解碼：

• 若 s[i-1] != '0'，可單獨解碼：dp[i] += dp[i-1]
• 若 10 <= s[i-2..i-1] <= 26，可組合解碼：dp[i] += dp[i-2]

O(1) 空間優化迭代實現 (Java)

public int numDecodings(String s) {
    int len = s.length();
    if (len == 0) return 0;
    int prev = 1; // dp[i-2]
    int cur = s.charAt(0) > '0' ? 1 : 0; // dp[i-1]
    if (cur == 0) return 0;
    
    for (int i = 1; i < len; i++) {
        int temp = cur;
        int comp = Integer.parseInt(s.substring(i-1, i+1));
        
        if (s.charAt(i) == '0') {
            char c = s.charAt(i-1);
            if (c == '1' || c == '2') {
                cur = prev; // 必須組合解碼
                prev = temp;
                continue;
            } else return 0; // 無效編碼
        } else if (comp < 10 || comp > 26) {
            prev = temp; // 只能單獨解碼
            continue;
        }
        cur += prev; // 兩種情況均可
        prev = temp;
    }
    return cur;
}

關鍵邊界情況處理

1. 前導零：字符串以 '0' 開頭直接返回 0
2. 孤立零：'0' 前必須是 '1' 或 '2'，否則無解
3. 兩位數範圍：10~26 才可組合，01~09、27~99 不可

複雜度分析

• 時間複雜度：O(n)，單次遍歷
• 空間複雜度：O(1)，僅使用兩個變量滾動