Decode Ways

PracticeNeetCode ↗LeetCode ↗

A digit string can be decoded using 'A' → "1", 'B' → "2", … 'Z' → "26". Given a string s of digits, return the number of ways it can be decoded. A leading zero in any two-digit group makes it invalid — "06" can't map to a letter.

Example

Key Pointers

• A '0' can never stand alone as a decoded digit — it's only valid as the second character of a two-digit code (10 or 20).
• The number of ways to decode from position i onward depends only on whether the next one or two digits form valid codes — the same "look back one or two steps" shape as Climbing Stairs.
• Working backward from the end of the string avoids needing a sentinel for "before the string starts."

Step-by-Step Analysis

1. Set up two running values representing "ways to decode the empty suffix past the end" (1) and an unused placeholder one position further (0).
2. Walk backward from the last character to the first. If the current digit is '0', there are 0 ways starting there.
3. Otherwise, start the count as the "ways from one position ahead" value (treating the digit as a single-digit code).
4. If the two-digit number formed with the next digit is between 10 and 26, add the "ways from two positions ahead" value too (treating it as a two-digit code).
5. Shift the running values forward for the next (earlier) index; the final value after the loop is the answer.

Complexity

Time: O(n) — Space: O(1)

Code

def numDecodings(s: str) -> int:
    if not s:
        return 0

    next1, next2 = 1, 0
    for i in range(len(s) - 1, -1, -1):
        current = 0
        if s[i] != "0":
            current = next1
            if i + 1 < len(s) and 10 <= int(s[i : i + 2]) <= 26:
                current += next2
        next1, next2 = current, next1

    return next1

Code Explanation

How the solution above works, piece by piece.

1. Work from the end: ways(i) = number of ways to decode s[i:]. The empty suffix has exactly 1 way (next1 = 1 at the start).
2. A digit that isn't '0' can be read alone, adding ways(i + 1).
3. If the two digits s[i:i+2] form 10–26, they can also be read together, adding ways(i + 2).
4. A '0' can't start a code, so current stays 0 there.
5. next1 and next2 hold ways(i+1) and ways(i+2): O(n) time, O(1) space.

Visual Walkthrough

Running it on s = "226":

Video Explanation

NeetCode — Decode Ways, LeetCode 91