Decode Ways in a Coding Interview: From Recursion to O(1) Space

"A message of digits was encoded with A=1 ... Z=26. How many ways can it be decoded?" Decode Ways is a favorite because it tests whether you can turn a messy counting problem into a clean recurrence, and because it is full of edge cases around zeros.

Clarify first

Ask these before writing anything:

  • Can the string start with 0? (Then the answer is 0.)
  • Is the empty string valid? (Usually return 0 for empty input, but confirm.)
  • Do we return a count, or the actual decodings? (A count. Listing them is exponential.)

The recurrence

Let ways(i) be the number of ways to decode the suffix starting at index i.

  • If s[i] == '0', nothing starts with zero, so ways(i) = 0.
  • Otherwise take one digit: ways(i) += ways(i + 1).
  • If s[i:i+2] is between 10 and 26, also take two digits: ways(i) += ways(i + 2).
  • Base case: ways(len(s)) = 1.

Plain recursion repeats work like Fibonacci does, so memoize it or go bottom-up.

Bottom-up with two variables

⎗
✓
def num_decodings(s):
    if not s or s[0] == '0':
        return 0
    nxt, nxt2 = 1, 0   # ways(i+1), ways(i+2)
    for i in range(len(s) - 1, -1, -1):
        cur = 0
        if s[i] != '0':
            cur = nxt
            if i + 1 < len(s) and 10 <= int(s[i:i+2]) <= 26:
                cur += nxt2
        nxt, nxt2 = cur, nxt
    return nxt

O(n) time, O(1) space. Mention that you went from memoized recursion to tabulation to two variables; interviewers like hearing the progression.

Test cases to say out loud

Input Answer Why
"12" 2 1,2 or 12
"226" 3 2,2,6 / 22,6 / 2,26
"06" 0 leading zero
"10" 1 only 10
"100" 0 00 can't decode
"27" 1 27 is out of range

The "100" case catches most bugs, so run it by hand.

Follow-ups

  1. Decode Ways II: * can be any digit 1-9. Same recurrence, but each step multiplies by the number of matching choices, and you take results mod 1e9+7.
  2. Return all decodings: switch to backtracking and warn that output size can be exponential.
  3. Streaming input: the two-variable version already works one character at a time.

Disclosure: I'm on the team behind Linkjob AI coding interview copilot, an AI assistant for technical interviews. This walkthrough is meant to be useful on its own.

Edit

Pub: 02 Nov 2026 16:05 UTC

Views: 7