91. Decode Ways
一個包含 A-Z 字母的消息可以使用以下映射編碼成數字：
'A' -> "1" 'B' -> "2" ... 'Z' -> "26" 要解碼編碼消息，必須將所有數字分組，然後使用上述映射的反向映射回字母（可能有多種方式）。例如，“11106” 可以映射成：
使用分組（1 1 10 6）得到 "AAJF" 使用分組（11 10 6）得到 "KJF" 注意，分組（1 11 06）無效，因為 “06” 不能映射成 'F'，因為 “6” 與 “06” 不同。
給定一個只包含數字的字符串 s，返回解碼它的方式數量。
測試用例生成的答案符合 32 位整數。
範例 1：
輸入：s = "12" 輸出：2 解釋："12" 可以解碼為 "AB" (1 2) 或 "L" (12)。
Python
class Solution:
def numDecodings(self, s: str) -> int:
if not s or s[0] == '0':
return 0
n = len(s)
dp = [0] * (n + 1)
dp[0] = 1 # There's one way to decode an empty string
dp[1] = 1 # There's one way to decode a non-zero single digit
for i in range(2, n + 1):
one_digit = int(s[i-1:i])
two_digits = int(s[i-2:i])
if 1 <= one_digit <= 9:
dp[i] += dp[i-1]
if 10 <= two_digits <= 26:
dp[i] += dp[i-2]
return dp[n]
16.41MB, 35ms
C++
#include <string>
#include <vector>
using namespace std;
class Solution {
public:
int numDecodings(string s) {
if (s.empty() || s[0] == '0') {
return 0;
}
int n = s.length();
vector<int> dp(n + 1, 0);
dp[0] = 1; // There's one way to decode an empty string
dp[1] = 1; // There's one way to decode a non-zero single digit
for (int i = 2; i <= n; ++i) {
int oneDigit = stoi(s.substr(i - 1, 1));
int twoDigits = stoi(s.substr(i - 2, 2));
if (oneDigit >= 1 && oneDigit <= 9) {
dp[i] += dp[i - 1];
}
if (twoDigits >= 10 && twoDigits <= 26) {
dp[i] += dp[i - 2];
}
}
return dp[n];
}
};
9.22MB, 0ms
Javascript
/**
* @param {string} s
* @return {number}
*/
var numDecodings = function(s) {
if (s.length === 0 || s[0] === '0') {
return 0;
}
const n = s.length;
const dp = new Array(n + 1).fill(0);
dp[0] = 1; // There's one way to decode an empty string
dp[1] = 1; // There's one way to decode a non-zero single digit
for (let i = 2; i <= n; i++) {
const oneDigit = parseInt(s.slice(i - 1, i));
const twoDigits = parseInt(s.slice(i - 2, i));
if (oneDigit >= 1 && oneDigit <= 9) {
dp[i] += dp[i - 1];
}
if (twoDigits >= 10 && twoDigits <= 26) {
dp[i] += dp[i - 2];
}
}
return dp[n];
};
48.90MB, 56ms
