Decode Ways

Problem

A digit string is encoded from letters A-Z as "1"-"26". Given an encoded string of digits, count the number of ways to decode it.

Input:  s = "226"
Output: 3   ("2 2 6", "22 6", "2 26")

Python Solution

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_digit = int(s[i - 1:i])
        two_digit = int(s[i - 2:i])
        if one_digit >= 1:
            dp[i] += dp[i - 1]
        if 10 <= two_digit <= 26:
            dp[i] += dp[i - 2]
    return dp[n]

C++ Solution

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 oneDigit = s[i - 1] - '0';
        int twoDigit = (s[i - 2] - '0') * 10 + (s[i - 1] - '0');
        if (oneDigit >= 1) dp[i] += dp[i - 1];
        if (twoDigit >= 10 && twoDigit <= 26) dp[i] += dp[i - 2];
    }
    return dp[n];
}

Java Solution

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 oneDigit = s.charAt(i - 1) - '0';
            int twoDigit = (s.charAt(i - 2) - '0') * 10 + (s.charAt(i - 1) - '0');
            if (oneDigit >= 1) dp[i] += dp[i - 1];
            if (twoDigit >= 10 && twoDigit <= 26) dp[i] += dp[i - 2];
        }
        return dp[n];
    }
}

Complexity

Time: O(n) — one pass, checking the last one and two digits at each position. Space: O(n) for the DP array; reducible to O(1) since only the previous two values are ever needed.