91. 解碼方法
題目鏈接： 91. 解碼方法
題目敘述： 一條包含字母 A-Z 的消息通過以下映射進行了 編碼 ：
“1” -> ‘A’
“2” -> ‘B’
…
“25” -> ‘Y’
“26” -> ‘Z’
然而，在解碼已編碼的消息時，你意識到有許多不同的方式來解碼，因為有些編碼被包含在其它編碼當中（“2” 和 “5” 與 “25”）。
例如，11106可以映射為：
"AAJF" ，將消息分組為 (1, 1, 10, 6)
"KJF" ，將消息分組為 (11, 10, 6)
消息不能分組為 (1, 11, 06) ，因為 “06” 不是一個合法編碼（只有 “6” 是合法的）。
注意，可能存在無法解碼的字符串。
給你一個只含數字的 非空 字符串 s，請計算并返回 解碼 方法的 總數 。如果沒有合法的方式解碼整個字符串，返回 0。
題目數據保證答案肯定是一個 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 = “06”
輸出： 0
解釋： “06” 無法映射到 “F” ，因為存在前導零（“6” 和 “06” 并不等價）。
提示：
1 <=s.length<= 100
s 只包含數字，并且可能包含前導零。
💦 前提注意： 這道題的s是一個非空字符串，而不是數組，所以計算時應減去'0'
解題思路：
- 狀態表示
dp[i]表示：以i位置為結尾時，所有解碼方法的總數 - 狀態轉移方程
根據最近的一步，劃分問題
其中a表示s[i]位置的數，b表示s[i-1]位置的數
dp[i] = dp[i-1] + dp[i-2] - 初始化
保證填表時不越界
以0位置結尾時說明此時只解碼了一個字符
以1位置結尾時說明此時解碼了兩個字符
- 填表順序
從左向右 - 返回值
dp[n-1]
代碼實現：
class Solution {
public:int numDecodings(string s) {//創建dp表//初始化//填表//返回值int n = s.size();vector<int> dp(n);dp[0] = s[0] != '0';//處理邊界條件if (n == 1) return dp[0];if (s[0] != '0' && s[1] != '0') dp[1] += 1;//第一個位置能單獨解碼，并且第二個位置也能單獨解碼int t = (s[0] - '0') * 10 + s[1] - '0';//前兩個位置所表示的數if (t >= 10 && t <= 26) dp[1] += 1;for (int i = 2; i < n; i++){if (s[i] != '0') dp[i] += dp[i - 1];//處理單獨解碼的情況int t = (s[i - 1] - '0') * 10 + s[i] - '0';//第二種情況所對應的數if (t >= 10 && t <= 26) dp[i] += dp[i - 2];}return dp[n - 1];}
細節優化：
處理邊界問題以及初始化問題的技巧
- 我們可以開一個比舊的表多1個的新的
dp表，使得舊dp表下標為0的位置，映射到新的dp表下標為1的位置，舊的下標為1的位置映射到新的下標為2的位置…依次類推。
- 這樣以來
dp[i]就可以表示為以第i個字符為終點的解碼方法的個數。所以就只需要初始化第1的字符即可。 - 這里有個小細節，我們在初始化
dp[0]這個虛擬節點時要將它初始化成1，比如只有兩個字符我們要判斷時 ,第二個字符單獨解碼時的方法數為1,第二個字符與第一個字符共同解碼時的方法總數應該為2，dp[2] = dp[1] + dp[0],我們可以將dp[0]給反推出來，所以dp[0]應該初始化為1
代碼實現：
class Solution {
public:int numDecodings(string s) {//創建dp表//初始化//填表//返回值int n = s.size();//創建dp表vector<int> dp(n+1);dp[0] = 1;dp[1] = s[0] != '0';for(int i = 2;i <= n;i++){if(s[i-1] != '0') dp[i]+=dp[i-1];int b = 10*(s[i-2]-'0') + (s[i -1] - '0');if(b>=10 && b <= 26) dp[i]+=dp[i- 2];}return dp[n];}
};
