Decode Ways — Counting Valid Decodings with Conditional Fibonacci DP

Problem Statement#

A message containing letters from A-Z can be encoded into numbers using the mapping A -> "1", B -> "2", ..., Z -> "26". To decode an encoded message, all the digits must be grouped then mapped back into letters. Given a string s containing only digits, return the number of ways to decode it. If there are no valid ways to decode the message, return 0.

Constraints:

• 1 <= s.length <= 100
• s contains only digits and may contain leading zeros.

Example 1:

Input:  s = "12"
Output: 2
Explanation: "12" can be decoded as "AB" (1 2) or "L" (12). Two ways.

Example 2:

Input:  s = "226"
Output: 3
Explanation: "226" can be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6). Three ways.

Example 3:

Input:  s = "06"
Output: 0
Explanation: "06" cannot be mapped to "F" (6) because the leading zero makes "06" an invalid encoding.
             "0" alone has no valid mapping.

Why This Problem Matters#

Decode Ways (LeetCode 91) is one of the most frequently asked medium DP problems at Amazon, Google, and Meta. It appears in the Blind 75 problem set and is used specifically to test conditional Fibonacci DP — where the standard dp[i] = dp[i-1] + dp[i-2] recurrence applies only when certain validity conditions are met.

The problem is deceptively complex because of edge cases involving zeros: "0" has no mapping, "30" cannot split as 3+0 (0 is invalid), but "20" can map to "T" (20) as a two-digit decode. These edge cases are where most candidates introduce bugs, which is exactly why interviewers use this problem to assess careful thinking under time pressure.

Mastering Decode Ways also gives you the framework to solve the even harder Decode Ways II (LC 639), which introduces wildcard characters.

The Core Insight#

Define dp[i] as the number of ways to decode the first i characters of s (i.e., s[0..i-1]).

At position i, you have at most two choices:

One-digit decode: Decode s[i-1] as a single digit. Valid only if s[i-1] != '0' (since '0' has no mapping). If valid: dp[i] += dp[i-1].

Two-digit decode: Decode s[i-2..i-1] as a two-digit number. Valid only if 10 <= int(s[i-2:i]) <= 26. If valid: dp[i] += dp[i-2].

This is the Climbing Stairs recurrence — dp[i] = dp[i-1] + dp[i-2] — but with conditional additions based on digit validity.

Base cases:

• dp[0] = 1 — one way to decode an empty string (the empty decoding).
• dp[1] = 1 if s[0] != '0', else dp[1] = 0.

Key insight about the two-digit validity check:

• Lower bound 10: a two-digit sequence starting with '0' (like "01", "07") is invalid — the encoding never starts with 0.
• Upper bound 26: "27" through "99" have no corresponding letter.
• So valid two-digit sequences are "10" through "26".

Building the DP Solution#

Step 1 — Naive Recursion (Exponential)#

# Python — naive recursion, exponential — illustrative only
def numDecodings(s):
    def dp(i):
        if i == 0:
            return 1  # empty prefix: one valid decoding
        if s[i - 1] == '0':
            # Check if it's a valid 2-digit
            if i >= 2 and 10 <= int(s[i-2:i]) <= 26:
                return dp(i - 2)
            return 0
        # Single digit valid
        result = dp(i - 1)
        # Two-digit check
        if i >= 2 and 10 <= int(s[i-2:i]) <= 26:
            result += dp(i - 2)
        return result
    return dp(len(s))

// JavaScript — naive recursion
function numDecodings(s) {
    function dp(i) {
        if (i === 0) return 1;
        if (s[i - 1] === '0') {
            if (i >= 2) {
                const two = parseInt(s.slice(i - 2, i));
                if (two >= 10 && two <= 26) return dp(i - 2);
            }
            return 0;
        }
        let result = dp(i - 1);
        if (i >= 2) {
            const two = parseInt(s.slice(i - 2, i));
            if (two >= 10 && two <= 26) result += dp(i - 2);
        }
        return result;
    }
    return dp(s.length);
}

Step 2 — Top-Down Memoization (O(n) time, O(n) space)#

# Python — top-down memoization
from functools import lru_cache
 
class Solution:
    def numDecodings(self, s: str) -> int:
        @lru_cache(maxsize=None)
        def dp(i: int) -> int:
            if i == 0:
                return 1
            if s[i - 1] == '0':
                # Current char is '0'; only valid as second digit of two-digit
                if i >= 2 and 10 <= int(s[i-2:i]) <= 26:
                    return dp(i - 2)
                return 0
            result = dp(i - 1)  # single-digit decode
            if i >= 2 and 10 <= int(s[i-2:i]) <= 26:
                result += dp(i - 2)  # two-digit decode
            return result
 
        return dp(len(s))

// JavaScript — top-down memoization
var numDecodings = function(s) {
    const memo = new Map();
 
    function dp(i) {
        if (i === 0) return 1;
        if (memo.has(i)) return memo.get(i);
 
        let result = 0;
        if (s[i - 1] !== '0') {
            result += dp(i - 1);  // single-digit decode
        }
        if (i >= 2) {
            const two = parseInt(s.slice(i - 2, i));
            if (two >= 10 && two <= 26) {
                result += dp(i - 2);  // two-digit decode
            }
        }
 
        memo.set(i, result);
        return result;
    }
 
    return dp(s.length);
};

Step 3 — Bottom-Up Tabulation (O(n) time, O(n) space)#

# Python — bottom-up tabulation
class Solution:
    def numDecodings(self, s: str) -> int:
        n = len(s)
        dp = [0] * (n + 1)
        dp[0] = 1
        dp[1] = 0 if s[0] == '0' else 1
 
        for i in range(2, n + 1):
            # One-digit decode: s[i-1]
            if s[i - 1] != '0':
                dp[i] += dp[i - 1]
            # Two-digit decode: s[i-2:i]
            two_digit = int(s[i-2:i])
            if 10 <= two_digit <= 26:
                dp[i] += dp[i - 2]
 
        return dp[n]

// JavaScript — bottom-up tabulation
var numDecodings = function(s) {
    const n = s.length;
    const dp = new Array(n + 1).fill(0);
    dp[0] = 1;
    dp[1] = s[0] === '0' ? 0 : 1;
 
    for (let i = 2; i <= n; i++) {
        // One-digit decode
        if (s[i - 1] !== '0') dp[i] += dp[i - 1];
        // Two-digit decode
        const two = parseInt(s.slice(i - 2, i));
        if (two >= 10 && two <= 26) dp[i] += dp[i - 2];
    }
 
    return dp[n];
};

Optimized Solution#

Since dp[i] depends only on dp[i-1] and dp[i-2], use two rolling variables:

# Python — space-optimized, O(n) time, O(1) space
class Solution:
    def numDecodings(self, s: str) -> int:
        if s[0] == '0':
            return 0
        prev2, prev1 = 1, 1  # dp[0], dp[1]
 
        for i in range(2, len(s) + 1):
            curr = 0
            if s[i - 1] != '0':
                curr += prev1
            two_digit = int(s[i-2:i])
            if 10 <= two_digit <= 26:
                curr += prev2
            prev2, prev1 = prev1, curr
 
        return prev1

// JavaScript — space-optimized, O(n) time, O(1) space
var numDecodings = function(s) {
    if (s[0] === '0') return 0;
    let prev2 = 1, prev1 = 1;
 
    for (let i = 2; i <= s.length; i++) {
        let curr = 0;
        if (s[i - 1] !== '0') curr += prev1;
        const two = parseInt(s.slice(i - 2, i));
        if (two >= 10 && two <= 26) curr += prev2;
        [prev2, prev1] = [prev1, curr];
    }
 
    return prev1;
};

Visual Dry Run#

Input: s = "226"

Base: dp[0] = 1, dp[1] = 1 (s[0]='2', not '0')

Answer: 3. The three decodings are: (2)(2)(6)=BBF, (22)(6)=VF, (2)(26)=BZ.

Input: s = "06" (edge case)

Base: dp[0] = 1, dp[1] = 0 (s[0]='0' → invalid single digit)

Answer: 0. Correct — "06" starts with 0.

Complexity Analysis#

Common Mistakes#

1. Not checking s[0] == '0' as an early exit. If the string starts with '0', there is no valid single-digit decoding for the first character and no valid two-digit prefix. Return 0 immediately.

2. Checking two_digit <= 26 without checking two_digit >= 10. The two-digit sequence "09" = 9, which is out of range (9 < 10). The lower bound check is essential to exclude zero-padded values.

3. Treating '0' as a valid single digit. '0' has no mapping. If s[i-1] == '0', the one-digit contribution is 0. Skip the single-digit addition.

4. Off-by-one in two-digit access. Two digits at position i (1-indexed) are s[i-2] and s[i-1] (0-indexed), or s[i-2:i] as a slice. Using s[i-1:i+1] instead shifts by one.

5. Initializing prev1 = 1 even when s[0] == '0'. If s[0] == '0', dp[1] = 0, not 1. Always set prev1 = 0 if s[0] == '0' else 1.

6. Forgetting that "10" and "20" are valid two-digit but not valid as two separate single digits. "10" decodes as "J" (10). "1" and "0" is invalid (0 has no mapping). The two-digit check enables "10" while the single-digit check (s[i-1] != '0') disables the '0' branch.

Interview Tips#

Walk through the two conditions explicitly. Say: "At each position, I check two things: (1) can I decode the current character as a single digit? Only if it's not '0'. (2) Can I decode the last two characters as a two-digit number? Only if the value is between 10 and 26."

Handle zeros carefully and explicitly. Tell your interviewer: "Zeros are the trickiest part. A lone '0' has no valid mapping. A '0' at the start of a two-digit sequence (like '07') is also invalid — it's not in the range 10-26. Only '10' and '20' are valid two-digit sequences ending in 0."

Connect to Climbing Stairs. "This is like Climbing Stairs but with conditional steps — sometimes the 1-step or 2-step transition is invalid based on the digit values."

Mention Decode Ways II. "The follow-up LC 639 introduces '*' wildcards that can represent any digit 1-9. The DP structure is the same but each validity check fans out into multiple cases."

Follow-up Questions#

Q: What if the string contains wildcard characters '*' (Decode Ways II, LC 639)? A '' can represent any digit 1-9. For single-digit decodes, a '' contributes 9 times dp[i-1]. For two-digit decodes, the multiplier depends on whether the first or second character is a wildcard.

Q: What if you need to output all actual decodings, not just the count? Use DFS/backtracking: at each position, try one-digit and two-digit splits recursively. Collect all paths that decode the full string.

Q: What if the character set extends beyond 26 (e.g., A-Z + aa-zz for 52 letters)? Extend the two-digit check to allow values up to 52, and add a three-digit check for values up to 52 if the encoding uses three-digit numbers.

Q: What if you want the number of decodings modulo 10^9 + 7? Add % (10**9 + 7) to the update. Python handles this natively; other languages need care with overflow.

Q: Can this be solved without DP? The counting structure has overlapping subproblems (substrings with the same suffix), so DP (or equivalently, memoization) is required for O(n) time. No greedy shortcut exists.

Key Takeaways#

• Define dp[i] as the number of ways to decode s[0..i-1]. Base: dp[0] = 1, dp[1] = 0 or 1 depending on s[0].
• Recurrence: if s[i-1] != '0', add dp[i-1] (one-digit); if 10 <= int(s[i-2:i]) <= 26, add dp[i-2] (two-digit).
• The conditions are critical — omitting either the != '0' check or the 10-26 range check produces wrong counts.
• Space-optimize with two rolling variables prev2 and prev1, identical to the Climbing Stairs optimization.
• The trickiest edge cases involve zeros: strings starting with '0' return 0, and '0' within a string can only be the second digit of "10" or "20".
• This is a conditional Fibonacci DP — the Climbing Stairs recurrence applies only when validity conditions are satisfied. Recognizing this connection makes the problem tractable.