解碼方法數問題
解碼方法數問題
作者：Grey
原文地址：
題目描述
一條包含字母 A-Z 的消息通過以下映射進行了 編碼 ：
‘A’ -> 1
‘B’ -> 2
…
‘Z’ -> 26
要 解碼 已編碼的消息，所有數字必須基於上述映射的方法，反向映射回字母（可能有多種方法）。例如，”11106″ 可以映射為：
“AAJF” ，將消息分組為 (1 1 10 6)
“KJF” ，將消息分組為 (11 10 6)
注意，消息不能分組為 (1 11 06) ，因為 “06” 不能映射為 “F” ，這是由於 “6” 和 “06” 在映射中並不等價。
給你一個只含數字的 非空 字元串 s ，請計算並返回 解碼 方法的 總數 。
題目數據保證答案肯定是一個 32 位 的整數。
示例 1：
輸入：s = “12”
輸出：2
解釋：它可以解碼為 “AB”（1 2）或者 “L”（12）。
示例 2：
輸入：s = “226”
輸出：3
解釋：它可以解碼為 “BZ” (2 26), “VF” (22 6), 或者 “BBF” (2 2 6) 。
示例 3：
輸入：s = “0”
輸出：0
解釋：沒有字元映射到以 0 開頭的數字。
含有 0 的有效映射是 ‘J’ -> “10” 和 ‘T’-> “20” 。
由於沒有字元，因此沒有有效的方法對此進行解碼，因為所有數字都需要映射。
示例 4：
輸入：s = “06”
輸出：0
解釋：”06″ 不能映射到 “F” ，因為字元串含有前導 0（”6″ 和 “06” 在映射中並不等價）。
暴力遞歸解
定義遞歸函數int process(int i, char[] str)
遞歸含義表示：從 i 一直到最後，得到的解碼方法數有多少
base case 是：
當 i 已經大於 str.length，說明之前的解碼決策有問題，直接返回 0。
當 i 正好等於 str.length, 說明之前的決策正好有一種符合條件的情況，返回 1。
接下來就是普遍情況，即：i 小於 str.length, 此時，有如下幾種決策情況
第一種情況
str[i]=='0'，由於 0 無法解碼成任何字元，也無法和後一個進行拼湊成一個字元的編碼，所以，直接返回 0。表示決策無效。
第二種情況
str[i] == '1', 則可以有如下決策，首先，str[i]位置獨立編碼成一個字元，或者str[i]和str[i+1]結合解碼成一個字元。
第三種情況
str[i] == '2', 則可以有如下決策，首先，str[i]位置獨立編碼成一個字元，或者str[i]和str[i+1]結合解碼成一個字元,但是此時的str[i+1]的字元有條件，即:
i + 1 < str.length && str[i + 1] <= '6'
只有滿足這個條件，str[i]才能和str[i+1]結合解碼成一個字元。
第四種情況
str[i] > '2', 則str[i]只能單獨解碼成一個字元。
暴力解法的完整程式碼如下
class Solution {
public static int numDecodings(String s) {
if (null == s || s.length() < 1) {
return 0;
}
char[] str = s.toCharArray();
return process(0, str);
}
// 從i一直到最後，得到的解碼數
public static int process(int i, char[] str) {
if (i > str.length) {
return 0;
}
if (i == str.length) {
return 1;
}
// i < str.length
if (str[i] == '0') {
return 0;
}
if (str[i] == '1') {
int p1 = process(i + 1, str);
int p2 = process(i + 2, str);
return p1 + p2;
}
if (str[i] == '2') {
int p1 = process(i + 1, str);
if (i + 1 < str.length && str[i + 1] <= '6') {
p1 += process(i + 2, str);
}
return p1;
}
return process(i + 1, str);
}
}
直接超時
動態規劃
有了上述暴力遞歸解法，可以直接改成動態規劃解法，由於遞歸函數只有一個可變參數，所以定義一個一維數組即可裝下所有可能性。
int[] dp = new int[str.length + 1];
dp[i]的含義和遞歸函數process(i,str)的含義一樣，都是從 i 開始到最後，解碼數量是多少。
由於暴力遞歸方法中，process(i,str)依賴process(i+1,str)和process(i+2,str)
所以對於 dp 數組來說， dp[i]的值依賴dp[i+1]和dp[i+2]決策的結果，
根據暴力遞歸方法中的 base case，可以得到 dp 的某些行列的初始值，然後根據遞推公式進行遞歸，最後返回dp[0]就是結果。
動態規劃解的完整程式碼如下
class Solution {
public static int numDecodings(String s) {
if (null == s || s.length() < 1) {
return 0;
}
char[] str = s.toCharArray();
int[] dp = new int[str.length + 1];
dp[str.length] = 1;
for (int i = str.length - 1; i >= 0; i--) {
if (str[i] == '0') {
dp[i] = 0;
} else {
dp[i] = dp[i + 1];
if (str[i] == '1' && i + 1 < str.length) {
dp[i] = dp[i] + dp[i + 2];
} else if (str[i] == '2' && i + 1 < str.length && str[i + 1] <= '6') {
dp[i] += dp[i + 2];
}
}
}
return dp[0];
}
}
