Problem 57 · Dynamic Programming

Decode Ways

MediumClassic DSA & systems

01Problem

A message of digits is encoded with A=1..Z=26. Return the number of ways to decode it.

02Key insight

Fibonacci-style DP: ways[i] = ways[i-1] if the single digit is 1-9, plus ways[i-2] if the two-digit number is 10-26. Zeros are the trap.

03Solution

solution.pypython10 lines

def num_decodings(s: str) -> int:
    if not s:
        return 0
    prev2, prev1 = 1, 1  # ways for s[:i-2], s[:i-1]
    for i in range(len(s)):
        cur = prev1 if s[i] != "0" else 0
        if i > 0 and 10 <= int(s[i - 1:i + 1]) <= 26:
            cur += prev2
        prev2, prev1 = prev1, cur
    return prev1

Try it first.

TimeO(n)

SpaceO(1)

tests.py · 4 passing

tests.pypython4 lines

assert num_decodings("12") == 2
assert num_decodings("226") == 3
assert num_decodings("06") == 0
assert num_decodings("10") == 1

04Staff-level follow-up

Count can be astronomically large for long inputs: return it mod 1e9+7, or for a streaming input keep just the two-state window as digits arrive.