Decode Ways
A message containing letters from A-Z can be encoded into numbers using the following mapping: 'A' ->200Question Mark, 'B' = 2, ..., 'Z' = 26. Given a non-empty string containing only digits, determine the number of ways to decode it.
Constraints:
- 1 <= s.length <= 100
- s contains only digits
Examples:
Input: 12
Output: 2
Explanation: It could be decoded as 'AB' (1 2) or 'L' (12)
Input: 226
Output: 3
Explanation: It could be decoded as 'BZ' (2 26), 'VF' (2 2 6), or 'BBF' (2 2 6)
Solutions
Dynamic Programming
This solution uses dynamic programming to calculate the number of ways to decode the string. It initializes a dp array where dp[i] represents the number of ways to decode the string up to index i. It then iterates through the string, updating dp[i] based on whether the current character can be decoded separately or together with the previous character.
function numDecodings(s) {
let dp = new Array(s.length + 1).fill(0);
dp[0] = 1;
for (let i = 1; i <= s.length; i++) {
if (s[i - 1] !== '0') dp[i] += dp[i - 1];
if (i >= 2 && s.slice(i - 2, i) >= '10' && s.slice(i - 2, i) <= '26')
dp[i] += dp[i - 2];
}
return dp[s.length];
}
Follow-up:
How would you modify the solution to handle cases where the input string contains non-digit characters?
