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 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.
Dry Run
s = "226"
| i | Substr | One Digit | Two Digit | dp[i] Logic | Result |
|---|---|---|---|---|---|
| 0 | "" | - | - | Base Case | 1 |
| 1 | "2" | "2" (Valid) | - | dp[1] += dp[0] |
1 |
| 2 | "22" | "2" (Valid) | "22" (Valid) | dp[2] += dp[1] + dp[2] += dp[0] |
2 |
| 3 | "226" | "6" (Valid) | "26" (Valid) | dp[3] += dp[2] + dp[3] += dp[1] |
3 |
Edge Cases & Common Mistakes
Watch out for these pitfalls:
A zero alone is nothing. "0", "06" and "100" all answer 0 — the zero has to be the second digit of 10 or 20 or the string is undecodable.
"27" is not a letter. The two-digit rule stops at 26. "27" decodes only as 2-7, so dp[i] gets dp[i-1] and nothing else.
Column i is the first i characters, not character i. dp has n + 1 entries and the digit at column i is s[i-1]. Nearly every wrong answer to this problem is this offset.
Solution
The two rules, applied once per prefix — the lines light up as the figure above steps.
Decode Ways Code
1var numDecodings = function(s) {2 const n = s.length;3 const dp = new Array(n + 1).fill(0);4 dp[0] = 1;5 for (let i = 1; i <= n; i++) {6 if (s[i - 1] !== '0') {7 dp[i] += dp[i - 1];8 }9 if (i > 1) {10 const pair = Number(s.slice(i - 2, i));11 if (pair >= 10 && pair <= 26) {12 dp[i] += dp[i - 2];13 }14 }15 }16 return dp[n];17};