LeetCode 筆記：Decode Ways - 解碼方法數動態規劃

題目描述

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

動態規劃分析

這本質上是「爬樓梯」變體：每一步可以走 1 格（單個數字 1-9）或 2 格（兩位數 10-26）。定義 dp[i] 為前 i 個字符的解碼數（dp[0]=1 空串視為 1 種）。轉移：

• 若第 i 個字符 !='0'，可單獨解碼：dp[i] += dp[i-1]。
• 若第 i-1, i 兩字符組成的兩位數在 10~26 之間，可合併解碼：dp[i] += dp[i-2]。

空間優化：只需保留前兩個狀態 prev (dp[i-2]) 和 cur (dp[i-1])。

代碼實現 (C++)

class Solution {
public:
    int numDecodings(string s) {
        if (s.empty() || s[0] == '0') return 0;
        int prev = 0, cur = 1; // dp[0]=1, dp[-1]=0 (虛擬)
        for (size_t i = 1; i <= s.size(); ++i) {
            if (s[i-1] == '0') cur = 0;               // 單獨不可解碼
            if (i < 2 || !(s[i-2] == '1' || (s[i-2] == '2' && s[i-1] <= '6')))
                prev = 0;                             // 兩位數不可合併
            int tmp = cur;
            cur = prev + cur;                         // 狀態轉移
            prev = tmp;
        }
        return cur;
    }
};

Java 版本

public class Solution {
    public int numDecodings(String s) {
        if (s == null || s.length() == 0 || s.charAt(0) == '0') return 0;
        int prev = 0, cur = 1;
        for (int i = 1; i <= s.length(); i++) {
            if (s.charAt(i-1) == '0') cur = 0;
            if (i < 2 || !(s.charAt(i-2) == '1' || (s.charAt(i-2) == '2' && s.charAt(i-1) <= '6')))
                prev = 0;
            int tmp = cur;
            cur = prev + cur;
            prev = tmp;
        }
        return cur;
    }
}

邊界情況處理

• 字符串以 '0' 開頭 → 0 種。
• 連續 '0' 或 '30','40' 等無法組成合法兩位數 → 中途 cur 歸零，最終結果為 0。
• 長度 1 的非零字符串 → 1 種。

複雜度

• 時間：O(n)
• 空間：O(1)

總結

本題將字符串解碼轉化為「每步走 1 或 2 格」的經典 DP，關鍵在於正確判斷單字符與雙字符的合法性，並用滾動變量優化空間。面試時可先寫 O(n) 空間版本講清遞推邏輯，再現場優化至 O(1)。