Decode Ways

Difficulty: Medium Source: NeetCode

Problem

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 mapped back into letters using the reverse of the mapping above. Given a string s containing only digits, return the number of ways to decode it. If there is no valid decoding, return 0.

Example 1: Input: s = "12" Output: 2 (“AB” or “L”)

Example 2: Input: s = "226" Output: 3 (“BZ”, “VF”, or “BBF”… wait — “226” → “B”,“B”,“F” or “V”,“F” or “B”,“Z”)

Example 3: Input: s = "06" Output: 0

Constraints:

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

Prerequisites

Before attempting this problem, you should be comfortable with:

• Dynamic Programming — building up counts of valid decodings
• String Parsing — checking single and two-digit validity
• Fibonacci-style DP — how previous two states feed into the current one

1. Brute Force (Recursion)

Intuition

At each position, try decoding a single digit (1-9) or a two-digit number (10-26). Recursively count all valid decodings. Without memoization, this recomputes the same substrings many times.

Algorithm

1. At each position i, check if s[i] is a valid single digit (not ‘0’).
2. Check if s[i:i+2] is a valid two-digit encoding (10-26).
3. Sum the results of valid recursive calls.

Solution

def numDecodings_brute(s):
    def dp(i):
        if i == len(s):
            return 1  # successfully decoded everything
        if s[i] == '0':
            return 0  # '0' can't start a valid encoding

        # Single-digit decode
        ways = dp(i + 1)

        # Two-digit decode
        if i + 1 < len(s) and 10 <= int(s[i:i + 2]) <= 26:
            ways += dp(i + 2)

        return ways

    return dp(0)


print(numDecodings_brute("12"))   # 2
print(numDecodings_brute("226"))  # 3
print(numDecodings_brute("06"))   # 0
print(numDecodings_brute("11106"))  # 2

Complexity

• Time: O(2^n) — two branches at each step
• Space: O(n) — recursion stack

2. Dynamic Programming (Bottom-Up)

Intuition

dp[i] = number of ways to decode the first i characters of s (i.e., s[:i]).

• dp[0] = 1 (empty string has one decoding — do nothing)
• dp[1] = 1 if s[0] != '0', else 0

Transitions:

• Single digit: if s[i-1] != '0', then dp[i] += dp[i-1] (the last character forms a valid letter)
• Two digits: if 10 <= int(s[i-2:i]) <= 26, then dp[i] += dp[i-2] (the last two characters form a valid letter)

Like House Robber, only the previous two values matter, so we can optimize to O(1) space.

Algorithm

1. Initialize dp1 = 1 (represents dp[i-1]), dp2 = 1 (represents dp[i-2]).
2. For each position i from 1 to n:
   • Compute curr = 0.
   • Single digit: if s[i-1] != '0', add dp1.
   • Two digits: if 10 <= int(s[i-2:i]) <= 26, add dp2.
   • Slide: dp2 = dp1, dp1 = curr.
3. Return dp1.

Solution

def numDecodings(s):
    n = len(s)
    if not s or s[0] == '0':
        return 0

    # dp1 = ways to decode s[:i-1], dp2 = ways to decode s[:i-2]
    dp1, dp2 = 1, 1  # dp[1] = 1, dp[0] = 1

    for i in range(2, n + 1):
        curr = 0

        # Single-digit decode of s[i-1]
        if s[i - 1] != '0':
            curr += dp1

        # Two-digit decode of s[i-2:i]
        two_digit = int(s[i - 2:i])
        if 10 <= two_digit <= 26:
            curr += dp2

        dp2 = dp1
        dp1 = curr

    return dp1


print(numDecodings("12"))      # 2
print(numDecodings("226"))     # 3
print(numDecodings("06"))      # 0
print(numDecodings("11106"))   # 2
print(numDecodings("10"))      # 1  ("J" only)
print(numDecodings("27"))      # 1  ("BG" only, 27 > 26)
print(numDecodings("2101"))    # 1

Complexity

• Time: O(n) — single pass
• Space: O(1) — rolling variables

Common Pitfalls

Not handling leading zeros. "06" should return 0 because ‘0’ alone is not valid, and “06” as a two-digit number isn’t valid (must be 10-26). Always check s[i-1] != '0' before the single-digit decode.

Two-digit range is 10-26, not 1-26. Numbers 01-09 are invalid two-digit encodings. Only 10-26 are valid. Checking int(s[i-2:i]) <= 26 alone isn’t enough — you need >= 10 too.

Confusing the DP index shift. dp[i] represents ways to decode s[:i] (the first i characters), not s[i]. So s[i-1] is the current character and s[i-2:i] is the two-character window.