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, soways(i) = 0. - Otherwise take one digit:
ways(i) += ways(i + 1). - If
s[i:i+2]is between10and26, 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
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
- 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. - Return all decodings: switch to backtracking and warn that output size can be exponential.
- 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.