Decode Ways (LeetCode 91)

The problem

Letters are encoded as numbers: A = 1, B = 2, …, Z = 26. Given a string s of digits, return how many ways it can be decoded back into letters. A code can’t have a leading zero, so "06" is not a valid code for F.

Input:  s = "226"
Output: 3

It can be read as 2 2 6 (BBF), 22 6 (VF) or 2 26 (BZ).

How to think about it

Start with brute force. At each position, try reading one digit, and also two digits if they form 10–26, then recurse on the rest. Each position can branch twice, so this is O(2ⁿ), with the same suffixes decoded over and over.

The key insight: it’s Climbing Stairs with rules. Look at the last code in any decoding of s[:i+1]. Either it is the single digit s[i], which is allowed only if s[i] != '0', or it is the pair s[i-1:i+1], allowed only if it is between 10 and 26. So ways[i] = (ways[i-1] if one digit is valid) + (ways[i-2] if the pair is valid). Without the checks this is exactly Fibonacci.

Two rolling variables again. cur is the count for the prefix ending at i-1, and prev the count one shorter. Each step builds tmp from whichever predecessors are valid, then shifts. Starting with prev = cur = 1 treats the empty prefix and the first digit as one way each, once you’ve checked that the first digit isn’t '0'.

Which pattern is this? 1-D DP over a string. The tell is “count the ways to split a sequence into pieces of length 1 or 2”, where some pieces are invalid.

Approach

1. If s is empty or starts with '0', return 0.
2. Set prev = 1 (empty prefix) and cur = 1 (first digit).
3. For each i from 1 to the end: start tmp = 0. If s[i] != '0', add cur. If s[i-1:i+1] is between 10 and 26, add prev. Then shift: prev, cur = cur, tmp.
4. Return cur.

Solution

def num_decodings(s):
    if not s or s[0] == '0': return 0             # nothing decodes a leading zero
    prev, cur = 1, 1                              # ways for prefix lengths i-1 and i
    for i in range(1, len(s)):
        tmp = 0
        if s[i] != '0': tmp += cur                # s[i] alone is a letter
        if 10 <= int(s[i-1:i+1]) <= 26: tmp += prev   # s[i-1:i+1] is a letter
        prev, cur = cur, tmp
    return cur
# num_decodings("226") -> 3  (BZ, VF, BBF)

Dry run

On s = "226":

The final cur is 3.

Complexity

• Time: O(n). One pass; each step does constant work.
• Space: O(1). Two counts and a temporary.

Edge cases and pitfalls

• Leading zero ("06") returns 0.
• Zeros mid-string must pair with the digit before: "10" returns 1, but "100" returns 0 because "00" isn’t valid and "0" alone isn’t either.
• Pairs like "27" or "30" are not valid two-digit codes; check the 10–26 range, not just “two digits”.
• Once cur hits 0 it stays 0 for good, which correctly reports an undecodable string.

Related problems

• Climbing Stairs (LeetCode 70): the same recurrence with every move allowed.
• Word Break (LeetCode 139): prefix DP where the pieces come from a dictionary.
• Letter Combinations of a Phone Number (LeetCode 17): digits to letters again, but listing every output with backtracking.