Decode Ways
Problem
A message of digits maps to letters by 1→A, 2→B, …, 26→Z. Count the number of ways to decode a given digit string. A leading 0 cannot stand alone or extend, except as part of 10 or 20.
Input
s = "226"Output
3"BZ", "VF", "BBF". dp[i] = (1-digit valid ? dp[i−1] : 0) + (2-digit valid ? dp[i−2] : 0).
def num_decodings(s):
if not s or s[0] == "0":
return 0
n = len(s)
dp = [0] * (n + 1)
dp[0] = dp[1] = 1
for i in range(2, n + 1):
one = int(s[i - 1])
two = int(s[i - 2:i])
if 1 <= one <= 9:
dp[i] += dp[i - 1]
if 10 <= two <= 26:
dp[i] += dp[i - 2]
return dp[n]function numDecodings(s) {
if (!s || s[0] === "0") return 0;
const n = s.length;
const dp = new Array(n + 1).fill(0);
dp[0] = dp[1] = 1;
for (let i = 2; i <= n; i++) {
const one = Number(s[i - 1]);
const two = Number(s.slice(i - 2, i));
if (one >= 1 && one <= 9) dp[i] += dp[i - 1];
if (two >= 10 && two <= 26) dp[i] += dp[i - 2];
}
return dp[n];
}class Solution {
public int numDecodings(String s) {
if (s.isEmpty() || s.charAt(0) == '0') return 0;
int n = s.length();
int[] dp = new int[n + 1];
dp[0] = dp[1] = 1;
for (int i = 2; i <= n; i++) {
int one = s.charAt(i - 1) - '0';
int two = Integer.parseInt(s.substring(i - 2, i));
if (one >= 1 && one <= 9) dp[i] += dp[i - 1];
if (two >= 10 && two <= 26) dp[i] += dp[i - 2];
}
return dp[n];
}
}int numDecodings(string s) {
if (s.empty() || s[0] == '0') return 0;
int n = s.size();
vector<int> dp(n + 1, 0);
dp[0] = dp[1] = 1;
for (int i = 2; i <= n; i++) {
int one = s[i - 1] - '0';
int two = stoi(s.substr(i - 2, 2));
if (one >= 1 && one <= 9) dp[i] += dp[i - 1];
if (two >= 10 && two <= 26) dp[i] += dp[i - 2];
}
return dp[n];
}