LeetCode 55 解碼方法 - 動態規劃處理字符串解碼

問題描述

字母 A-Z 編碼為 1-26。給定數字字符串，求解碼為字母字符串的方法數。例如 "12" 可解碼為 "AB"(1,2) 或 "L"(12)，共 2 種。注意：'0' 不能單獨解碼，只能作為 '10' 或 '20' 的一部分。

動態規劃解法

設 dp[i] 表示前 i 個字符（索引 0 到 i-1）的解碼方法數。

• dp[0] = 1（空串 1 種）。
• dp[1] = (s[0] == '0') ? 0 : 1。
• 對於 i ≥ 2：
  1. 單字符解碼：若 s[i-1] != '0'，dp[i] += dp[i-1]。
  2. 雙字符解碼：若 s[i-2..i-1] 在 "10" 到 "26" 之間，dp[i] += dp[i-2]。

最終返回 dp[n]。

代碼實現（C++）

class Solution {
public:
    int numDecodings(string s) {
        int n = s.size();
        if (n == 0) return 0;
        vector dp(n+1, 0);
        dp[0] = 1;
        dp[1] = s[0] == '0' ? 0 : 1;
        for (int i = 2; i <= n; i++) {
            // 單字符
            if (s[i-1] != '0') dp[i] = dp[i-1];
            // 雙字符
            int two = (s[i-2]-'0')*10 + (s[i-1]-'0');
            if (two >= 10 && two <= 26) dp[i] += dp[i-2];
        }
        return dp[n];
    }
};

關鍵點

• 處理 '0'：單獨 '0' 無效，必須與前一位組成 10 或 20。
• 初始條件 dp[0]=1 為了讓雙字符解碼時 dp[2] += dp[0] 正確計為 1。
• 可優化空間至 O(1)，只保留前兩個狀態。

複雜度

時間 O(n)，空間 O(n)（或 O(1) 優化）。