Decode Ways Solution

Problem

A string of digits encodes a message where 'A' maps to "1", 'B' to "2", and so on up to 'Z' mapping to "26". Given an encoded digit string, count how many distinct ways it can be decoded back into letters.

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

A counter-example: s = "06" returns 0 because '0' cannot stand alone as a letter, and "06" as a two-digit number equals 6, not a valid two-digit code (those start at 10).

Intuition

At every position in the string you face a binary choice: consume one digit or consume two. One digit is valid as long as it isn't '0'; two digits are valid only when they form a number between 10 and 26. The total count at the end is a sum of independent valid paths — exactly the structure dynamic programming is built for.

Approach 1 — Brute Force Recursion

At each index, recurse into the 1-digit branch (if the current character is not '0') and the 2-digit branch (if the next two characters form a number ≤ 26). Return 1 when the end is reached, 0 when a dead end is hit.

Base case: if index == len(s), return 1 (a complete valid decoding).
If s[index] == '0', return 0 — a standalone zero is not decodable.
Add the result of decoding from index + 1 (one-digit step).
If there is a next character and the two-digit substring is ≤ 26, also add the result of decoding from index + 2.
Return the total.

1def numDecodings(s: str) -> int:
2    def decode(index: int) -> int:
3        if index == len(s):
4            return 1  # reached end — this path is a valid decoding
5        if s[index] == '0':
6            return 0  # '0' can't start a new character on its own
7
8        ways = decode(index + 1)  # always try consuming one digit
9
10        if index + 1 < len(s) and int(s[index:index + 2]) <= 26:
11            ways += decode(index + 2)  # also try consuming two digits when valid
12
13        return ways
14
15    return decode(0)

Time: O(2^n) — each position branches into two recursive calls with no caching, so paths double at every step.
Space: O(n) — the recursion call stack grows to the length of the string.

Approach 2 — Bottom-Up DP (Space-Optimized)

Build the answer from left to right, keeping only the last two DP values instead of a full array — because dp[i] only ever reads dp[i-1] and dp[i-2].

Initialize prev2 = 1 (the empty-string base case) and prev1 = 0 if s[0] == '0' else 1.
For each position i from 2 to n (inclusive), compute current = 0.
If s[i-1] != '0', add prev1 — the current digit extends every prior decoding by one character.
If the two-digit window s[i-2:i] falls in [10, 26], add prev2 — the pair extends every decoding two steps back.
Slide the window: prev2 = prev1, prev1 = current.
Return prev1.

1def numDecodings(s: str) -> int:
2    prev2 = 1  # dp[i-2]: base case for empty string
3    prev1 = 0 if s[0] == '0' else 1  # dp[i-1]: single-character result
4
5    for i in range(2, len(s) + 1):
6        current = 0
7
8        if s[i - 1] != '0':
9            current += prev1  # one-digit extension is valid
10
11        two_digit = int(s[i - 2:i])
12        if 10 <= two_digit <= 26:
13            current += prev2  # two-digit extension is valid
14
15        prev2, prev1 = prev1, current
16
17    return prev1

Time: O(n) — a single pass through the string.
Space: O(1) — only two integer variables regardless of input length.

Complexity Summary

Approach	Time	Space	When to use
Brute Force Recursion	O(2^n)	O(n)	Understanding the problem structure; impractical for n > 20
Bottom-Up DP	O(n)	O(1)	Production: handles any length string efficiently

Common Mistakes

Treating '0' as a valid single-digit decode — the character '0' has no letter mapping, so any position where s[i] == '0' contributes zero one-digit ways; forgetting this turns inputs like "30" from 1 way into 2.
Capping the two-digit check at 99 instead of 26 — only letters A–Z exist, so the two-digit window must be ≤ 26; "27" through "99" are all invalid two-digit decodings.
Not enforcing a lower bound of 10 on the two-digit window — "06" equals 6, which is below 10, so it is not a valid two-digit code; using twoDigit <= 26 alone without twoDigit >= 10 silently accepts it.
Initializing the base case dp[0] to 0 — dp[0] represents the empty prefix and must be 1 (there is exactly one way to decode nothing), otherwise the two-digit branch always contributes 0.
Using a full dp array when two variables suffice — dp[i] only depends on dp[i-1] and dp[i-2], so carrying the entire array wastes O(n) space for no benefit.

Decode Ways — Solution