Decode Ways

Problem Statement

You’re a codebreaker with a string of digits, where each can be mapped to a letter (1=A, 2=B, ..., 26=Z). How many ways can you decode it into a message? Watch out for leading zeros and invalid pairs! This medium-level DP puzzle is a cryptographer’s playground—crack the code!

Example

Input: s = "12"

Output: 2 ("AB" or "L")

Input: s = "226"

Output: 3 ("BBF", "VF", "BF")

Input: s = "06"

Output: 0 (No valid decoding)

Code

public class Solution {
    public int numDecodings(String s) {
        int n = s.length();
        int[] dp = new int[n + 1];
        dp[0] = 1; // Empty string
        dp[1] = s.charAt(0) == '0' ? 0 : 1;
        for (int i = 2; i <= n; i++) {
            int oneDigit = s.charAt(i-1) - '0';
            int twoDigits = Integer.parseInt(s.substring(i-2, i));
            if (oneDigit >= 1) dp[i] += dp[i-1];
            if (twoDigits >= 10 && twoDigits <= 26) dp[i] += dp[i-2];
        }
        return dp[n];
    }
}
            

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, 1
    for i in range(2, n + 1):
        if s[i-1] != '0':
            dp[i] += dp[i-1]
        two_digits = int(s[i-2:i])
        if 10 <= two_digits <= 26:
            dp[i] += dp[i-2]
    return dp[n]
            

function numDecodings(s) {
    if (!s || s[0] === '0') return 0;
    let n = s.length;
    let dp = new Array(n + 1).fill(0);
    dp[0] = 1; dp[1] = 1;
    for (let i = 2; i <= n; i++) {
        if (s[i-1] !== '0') dp[i] += dp[i-1];
        let twoDigits = parseInt(s.slice(i-2, i));
        if (twoDigits >= 10 && twoDigits <= 26) dp[i] += dp[i-2];
    }
    return dp[n];
}
            

Explanation

• DP Insight: dp[i] = number of ways to decode s[0:i].
• Flow: For each position, add ways using the last digit and last two digits if valid.
• Edge Cases: Handle leading zeros and invalid pairs (e.g., "00", "30").
• Example Walkthrough: "226" → dp[1]=1 ("2"), dp[2]=2 ("22", "2"), dp[3]=3 ("226", "26", "22").
• Optimization: Can reduce to O(1) space with two variables.

Note