91. Decode Ways

← All Problems
medium Mixed Practice
Given a string s containing only digits, return the number of ways to decode it. The mapping is ‘A’ -> “1”, ‘B’ -> “2”, …, ‘Z’ -> “26”. A digit sequence may have multiple valid decodings — for example, “226” can be decoded as “BZ” (2,26), “VF” (22,6), or “BBF” (2,2,6). A string with leading zeros or invalid groupings (like “06”) has no valid decoding for that portion.

Example

s = "226"

Output: 3

The three valid decodings are: "2|2|6" = BBF, "22|6" = VF, and "2|26" = BZ. Each split uses only valid letter mappings (1-26).

dp[i] counts the number of ways to decode s[0:i]. If the single digit s[i-1] is valid (1-9), add dp[i-1] since you can decode it as one letter. If the two-digit number s[i-2:i] is valid (10-26), add dp[i-2] since you can decode those two characters as one letter. A leading zero means that single digit is invalid.

Why this works

At each position you have at most two choices: decode the current digit as one letter (1-9 maps to A-I), or decode the current and previous digit together as one letter (10-26 maps to J-Z). The total decodings at position i is the sum of decodings from both valid choices. Zeros can only appear as part of a two-digit code (10 or 20), never alone.

Step by step

  1. Set base cases — dp[0] = 1 (empty prefix has one trivial decoding), dp[1] depends on whether the first character is ‘0’.
  2. Check the single digit — if s[i-1] is 1-9, it maps to a letter, so add dp[i-1] (all ways to decode everything before it).
  3. Check the two-digit number — if s[i-2:i] is 10-26, those two characters map to one letter, so add dp[i-2].
  4. Return dp[n] — the total number of ways to decode the entire string.
Time: O(n) Space: O(n) 
class Solution {
    public int numDecodings(String s) {
        int n = s.length();
        int[] dp = new int[n + 1];
        dp[0] = 1; // base case: empty string has one way to decode
        dp[1] = s.charAt(0) != '0' ? 1 : 0;
        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 && oneDigit <= 9) { // valid single digit
                dp[i] += dp[i - 1];
            }
            if (twoDigits >= 10 && twoDigits <= 26) { // valid two-digit letter
                dp[i] += dp[i - 2];
            }
        }
        return dp[n];
    }
}

class Solution {
public:
    int numDecodings(string s) {
        int n = s.size();
        vector<int> dp(n + 1, 0);
        dp[0] = 1; // base case: empty string has one way to decode
        dp[1] = s[0] != '0' ? 1 : 0;
        for (int i = 2; i <= n; i++) {
            int oneDigit = s[i - 1] - '0';
            int twoDigits = stoi(s.substr(i - 2, 2));
            if (oneDigit >= 1 && oneDigit <= 9) { // valid single digit
                dp[i] += dp[i - 1];
            }
            if (twoDigits >= 10 && twoDigits <= 26) { // valid two-digit letter
                dp[i] += dp[i - 2];
            }
        }
        return dp[n];
    }
};

def numDecodings(s: str) -> int:
    n = len(s)
    dp = [0] * (n + 1)
    dp[0] = 1  # base case: empty string has one way to decode
    dp[1] = 1 if s[0] != '0' else 0  # '0' can't map to any letter
    for i in range(2, n + 1):
        one_digit = int(s[i - 1])
        two_digits = int(s[i - 2:i])
        if 1 <= one_digit <= 9:  # valid single digit → extend dp[i-1] decodings
            dp[i] += dp[i - 1]
        if 10 <= two_digits <= 26:  # valid two-digit letter → extend dp[i-2] decodings
            dp[i] += dp[i - 2]
    return dp[n]