題目
#

題目簡述
#

給一個包含數字的字串 s，該字串已經按照以下映射進行編碼：
'A' -> "1", 'B' -> "2", …, 'Z' -> "26"
要解碼已編碼的字串，必須將數字反向映射回包含大寫字母的字串。計算解碼方法的總數。

範例
#

Example 1:

Input: s = "12"
Output: 2
Explanation: "12" 可以被解碼為 "AB" (1 2) 或 "L" (12)。

Example 2:

Input: s = "226"
Output: 3
Explanation: "226" 可以被解碼為 "BZ" (2 26)、"VF" (22 6) 或 "BBF" (2 2 6)。

Example 3:

Input: s = "06"
Output: 0
Explanation: "06" 無法對應到 "F"，因為前面零的關係（"6" 與 "06" 不同）。

解題思路
#

這題要求我們計算一個數字字串的解碼方法數量。我們可以使用動態規劃來解決這個問題，通過建立一個 DP 陣列，其中 dp[i] 表示前 i 個字符的解碼方法數量。

解法
#

創建一個長度為 n+1 的 DP 陣列
初始化 dp[0] = 1（空字串有一種解碼方法）和 dp[1]（第一個字符的解碼方法）
對於每個位置 i，考慮兩種情況：
- 單獨解碼當前字符（如果不等於 ‘0’）
- 將當前字符與前一個字符組合解碼（如果在 10-26 範圍內）
返回 dp[n]

步驟
#

初始化 DP 陣列：
- 創建 int[] dp = new int[n+1]
- dp[0] = 1（空字串的解碼方法）
- dp[1] = s.charAt(0) != '0' ? 1 : 0（第一個字符的解碼方法）
填充 DP 陣列：
- 對於每個位置 i，檢查單獨解碼和組合解碼
- 如果當前字符不等於 ‘0’，加上 dp[i-1]
- 如果前兩個字符在 10-26 範圍內，加上 dp[i-2]
返回結果：
- 返回 dp[n]

例子說明
#

s = "226"

步驟	位置 i	當前字符	單獨解碼	組合解碼	DP 陣列	說明
初始化	-	-	-	-	`[1,0,0,0]`	`dp[0] = 1`
i=1	1	‘2’	可以	-	`[1,1,0,0]`	`dp[1] = 1`（‘2’ → ‘B’）
i=2	2	‘2’	可以	可以	`[1,1,2,0]`	單獨：‘2’ → ‘B’，組合：‘22’ → ‘V’
i=3	3	‘6’	可以	可以	`[1,1,2,3]`	單獨：‘6’ → ‘F’，組合：‘26’ → ‘Z’

最終結果： 3 種解碼方法

解碼方法：

"2" + "2" + "6" → “BBF”
"2" + "26" → “BZ”
"22" + "6" → “VF”

完整程式碼
#

java

class Solution {
    public int numDecodings(String s) {
        // 邊界檢查
        if (s == null || s.length() == 0) {
            return 0;
        }

        int n = s.length();
        int[] dp = new int[n + 1];

        // 初始化 DP 陣列
        dp[0] = 1; // 空字串有一種解碼方法
        dp[1] = s.charAt(0) != '0' ? 1 : 0; // 第一個字符的解碼方法

        // 填充 DP 陣列
        for (int i = 2; i <= n; i++) {
            // 單獨解碼當前字符
            if (s.charAt(i - 1) != '0') {
                dp[i] += dp[i - 1];
            }

            // 組合解碼：將當前字符與前一個字符組合
            int twoDigit = Integer.parseInt(s.substring(i - 2, i));
            if (twoDigit >= 10 && twoDigit <= 26) {
                dp[i] += dp[i - 2];
            }
        }

        return dp[n];
    }
}