LeetCode 91. 解碼方法【c++/java詳細題解】

本文收錄于LeetCode高頻面試題，480道后端面試高頻力扣題解，歡迎訂閱，

1、題目

一條包含字母 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" 在映射中并不等價），

2、思路

(動態規劃) O ( n ) O(n) O(n)

給定我們一個字串s，按照題目所給定的規則將其解碼，問一個字串可以有多少種不同的解碼方式，

樣例：

我們先來理解一下題目的解碼規則，如樣例所示，s = "226"，可以分為兩種情況：

• 1、將每一位數字單獨解碼，因此可以解碼成"BBF"(2 2 6)，
• 2、將相鄰兩位數字組合起來解碼（組合的數字范圍在10 ~ 26之間），因此可以解碼成"BZ"(2 26), "VF"(22 6)，

兩種情況是或的關系，互不影響，將其相加，那么226共有3種不同的解碼方式，下面來講解動態規劃的做法，

狀態表示：f[i]表示前i個數字一共有多少種解碼方式，那么，f[n]就表示前n個數字一共有多少種不同的解碼方式，即為答案，

狀態計算：

設定字串陣列為s[](陣列下標從1開始)，考慮最后一次解碼方式，因此對于第i - 1和第i個數字，分為兩種決策：

• 1、如果s[i]不為0，則可以單獨解碼s[i]，由于求的是方案數，如果確定了第i個數字的翻譯方式，那么解碼前i個數字和解碼前i - 1個數的方案數就是相同的，即f[i] = f[i - 1]，(s[]陣列下標從1開始)

• 2、將s[i]和s[i - 1]組合起來解碼（ 組合的數字范圍在10 ~ 26之間 ），如果確定了第i個數和第i - 1個數的解碼方式，那么解碼前i個數字和解碼前i - 2個數的方案數就是相同的，即f[i] = f[i - 2]，(s[]陣列下標從1開始)
  

最后將兩種決策的方案數加起來，因此，狀態轉移方程為： f[i] = f[i - 1] + f[i - 2]，

邊界條件：

f[0] = 1，解碼前0個數的方案數為1，

為什么解碼前0個數的方案數是1？

f[0]代表前0個數字的方案數，這樣的狀態定義其實是沒有實際意義的，但是f[0]的值需要保證邊界是對的，即f[1]和f[2]是對的，比如說，第一個數不為0，那么解碼前1個數只有一種方法，將其單獨解碼，即f[1] = f[1 - 1] = 1，解碼前兩個數，如果第1個數和第2個數可以組合起來解碼，那么f[2] = f[1] + f[0] = 2，否則只能單獨解碼第2個數，即f[2] = f[1] = 1，因此，在任何情況下f[0]取1都可以保證f[1]和f[2]是正確的，所以f[0]應該取1，

實作細節:

在推導狀態轉移方程時，我們假設的s[]陣列下標是從1開始的，而實際中的s[]陣列下標是從0開始的，為了一 一對應，我們需要將所有字串的下標減去 1，比如在取組合數字的值時，要取s[i - 2]和s[i - 1]，即組合值t = (s[i - 2] - '0') * 10 + s[i - 1] - '0'，

時間復雜度分析： 狀態數是 n n n 個，狀態轉移的時間復雜度是 O ( 1 ) O(1) O(1)，所以總時間復雜度是 O ( n ) O(n) O(n)，

空間復雜度分析： O ( n ) O(n) O(n)，

3、c++代碼

class Solution {
public:
    int numDecodings(string s) {
        int n = s.size();
        vector<int> f(n + 1);
        f[0] = 1;  // 邊界條件
        for(int i = 1; i <= n; i++){
            if(s[i - 1] != '0') f[i] = f[i - 1];         //單獨解碼s[i - 1]
            if(i >= 2){
                int t = (s[i - 2] - '0') * 10 + s[i - 1] - '0';
                if(t >= 10 && t <= 26) f[i] += f[i - 2]; //將s[i - 2] 和 s[i - 1]組合解碼
            }
        }
        return f[n];
    }
};

4、java代碼

class Solution {
    public int numDecodings(String s) {
        int n = s.length();
        int[] f = new int[n + 10];
        f[0] = 1;
        for(int i = 1; i <= n;i ++)
        {
            if(s.charAt(i - 1) != '0') f[i] += f[i - 1]; //單獨解碼s[i - 1]
            if(i >= 2)
            {
                int t = (s.charAt(i - 2) - '0') * 10 + s.charAt(i - 1) - '0';
                if(t >= 10 && t <= 26) f[i] += f[i - 2]; //將s[i - 2] 和 s[i - 1]組合解碼
            }
        }
        return f[n];
    }
}

原題鏈接：91. 解碼方法