FAANGPrep Sprint
Decode Ways
Determine the total number of ways to decode a string of digits into letters (A-Z).
Examples
"1 2" decodes as AB and "12" decodes as L.
2-2-6 is BBF, 22-6 is VF and 2-26 is BZ.
A leading zero is no letter on its own and cannot pair leftward, so nothing decodes.
Problem Understanding
We convert digits to letters: '1' -> 'A', '2' -> 'B', ..., '26' -> 'Z'. Given a string s, finding the count of possible decodings.
Example: s = "12"
- "1, 2" -> "AB"
- "12" -> "L"
- Output: 2
Algorithm Strategy
Let dp[i] be the number of ways to decode the first i characters. Every such decoding ends in one letter, and that letter used either one digit or two — the cases cannot overlap, so their counts add.
- One digit: if
s[i-1]is 1 to 9, adddp[i-1]. - Two digits: if
s[i-2..i-1]reads as 10 to 26, adddp[i-2].
Base case: dp[0] = 1. The empty prefix has exactly one decoding — the empty one.
Interactive Visualization
COLUMN i = THE FIRST i CHARACTERS · THE DIGIT ABOVE IT IS s[i−1] · COLUMN 0 IS THE EMPTY PREFIX
BASE CASE — THE EMPTY PREFIX
0
1
2
3
s
dp
digits
3
decided
1/4
Answer
—
the two rules
TWO DIGITS — s[i−2..i−1] IS 10 TO 26, ADD dp[i−2]
A 0 IS NEVER A LETTER ON ITS OWN
The empty prefix has exactly one decoding — the empty one — so dp[0] = 1
Next
Decode the first 1 character: "2". Start dp[1] at 0
message
Column i holds dp[i], the number of ways to decode the first i characters — so the digit drawn above it is s[i-1], and column 0 has no digit at all because it is the empty prefix. Each step outlines the cell being added in and the digit or pair it just read.
Try Zero: both rules refuse the leading zero, and the 0 carries all the way to the answer.