解碼方法數問題

作者：Grey

原文地址：

部落格園：解碼方法數問題

CSDN：解碼方法數問題

題目描述

一條包含字母 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" 在對映中並不等價）。

題目連結：LeetCode 91. Decode Ways

暴力遞迴解

定義遞迴函數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];
    }
}

演演算法和資料結構筆記

解碼方法數問題

解碼方法數問題

題目描述

暴力遞迴解

動態規劃

更多