Decode Ways

Problem Description

A message containing letters from A-Z can be encoded into numbers using the following mapping: 'A' -> "1", 'B' -> "2", …, 'Z' -> "26"

To decode an encoded message, all the digits must be grouped then mapped back into letters using the reverse of the mapping above (there may be multiple ways). For example, "11106" can be mapped into:

• "AAJF" with the grouping (1 1 10 6)
• "KJF" with the grouping (11 10 6)

Note that the grouping (1 11 06) is invalid because "06" cannot be mapped into 'F' since "6" is different from "06".

Given a string s containing only digits, return the number of ways to decode it.

The test cases are generated so that the answer fits in a 32-bit integer.

Examples

Constraints

• 1 ≤ s.length ≤ 100
• s contains only digits and may contain leading zero(s).

Branching Valid Digit Groups

At each character position i in the string, we must determine how many valid ways we can decode the prefix ending at i. We look at the preceding steps:

1. Single Digit: We can decode the single character at s[i - 1] as long as it is not '0'. This adds dp[i - 1] ways to our count.
2. Double Digit: We can decode the two-character block s[i - 2..i - 1] if it represents a valid number between 10 and 26. This adds dp[i - 2] ways to our count.

If a state fails these validation checks, it contributes 0 ways. For example, a leading zero can never be parsed as a valid single digit, so it immediately zeroes out the branch.

Because the calculation for dp[i] only depends on dp[i - 1] and dp[i - 2], we can optimize our space from O(n) to O(1) by storing only two tracking variables.

Solution 1: Dynamic Programming (Bottom-Up, Constant Space)

Iterate through the string, validating single-digit and double-digit groups to update state variables.

class Solution {
    public int numDecodings(String s) {
        if (s == null || s.length() == 0 || s.charAt(0) == '0') return 0;

        int prev2 = 1; // ways to decode empty prefix
        int prev1 = 1; // ways to decode prefix of length 1

        for (int i = 2; i <= s.length(); i++) {
            int current = 0;
            int singleDigit = s.charAt(i - 1) - '0';
            int doubleDigit = Integer.parseInt(s.substring(i - 2, i));

            // check if single digit is valid (1-9)
            if (singleDigit >= 1 && singleDigit <= 9) {
                current += prev1;
            }

            // check if double digit is valid (10-26)
            if (doubleDigit >= 10 && doubleDigit <= 26) {
                current += prev2;
            }

            // shift states
            prev2 = prev1;
            prev1 = current;
        }

        return prev1;
    }
}

class Solution:
    def numDecodings(self, s: str) -> int:
        if not s or s[0] == "0":
            return 0

        prev2 = 1  # ways to decode empty prefix
        prev1 = 1  # ways to decode prefix of length 1

        for i in range(2, len(s) + 1):
            current = 0
            single_digit = int(s[i - 1])
            double_digit = int(s[i - 2 : i])

            # check if single digit is valid (1-9)
            if 1 <= single_digit <= 9:
                current += prev1

            # check if double digit is valid (10-26)
            if 10 <= double_digit <= 26:
                current += prev2

            # shift states
            prev2 = prev1
            prev1 = current

        return prev1

#include <string>

class Solution {
public:
    int numDecodings(std::string s) {
        if (s.empty() || s[0] == '0') return 0;

        int prev2 = 1; // ways to decode empty prefix
        int prev1 = 1; // ways to decode prefix of length 1

        for (size_t i = 2; i <= s.length(); i++) {
            int current = 0;
            int singleDigit = s[i - 1] - '0';
            int doubleDigit = std::stoi(s.substr(i - 2, 2));

            // check if single digit is valid (1-9)
            if (singleDigit >= 1 && singleDigit <= 9) {
                current += prev1;
            }

            // check if double digit is valid (10-26)
            if (doubleDigit >= 10 && doubleDigit <= 26) {
                current += prev2;
            }

            // shift states
            prev2 = prev1;
            prev1 = current;
        }

        return prev1;
    }
};

Complexity Analysis:

• Time Complexity: O(n) where n is the length of string s. We scan the string once.
• Space Complexity: O(1) auxiliary space.

Where it breaks: If the string contains non-digit characters, the parsing step Integer.parseInt or std::stoi will throw exceptions. The constraints guarantee that s only contains digits.

Common Mistakes

• Not returning 0 immediately on leading zero. If s = "06", it cannot be decoded. You must check s[0] == '0' at the start.
• Adding to current when the double digit starts with 0. A double digit like "06" is invalid because leading zeros are not allowed. The condition doubleDigit >= 10 prevents this.
• Incorrectly initializing prev2 to 0. The empty prefix has exactly 1 valid way to be decoded (no characters consumed), which serves as the base multiplier.

Frequently Asked Questions

What does a value of 0 in the output mean? It means the string contains invalid sequences (like "30" or "06") that cannot be mapped to any characters, making the entire message undecodable.

Can we solve this using recursion with memoization? Yes. You can write a DFS helper that returns the number of ways starting from index i, caching results in a memo array to avoid O(2^n) time complexity.

What does this problem test in interviews? It tests your capability to write dynamic programming states with strict validation conditions and manage boundary checks on character indices.

← All Problems