Appearance
4.23.7 — Decode Ways
LeetCode 91 · Medium · ★ Blind 75
The problem
A is 1, B is 2, up to Z which is 26. Given a string of digits, how many ways can it be decoded?
"12" → 2 ("AB" = 1,2 or "L" = 12)
"226" → 3 ("BZ", "VF", "BBF")
"06" → 0 (no letter is 0, and "06" is not a valid 6)Restating the Problem: Imagine you intercept a secret numerical message where A=1, B=2 ... Z=26. Because there are no spaces between the numbers, the message is ambiguous. For example, 12 could be 1, 2 (A, B) or 12 (L). Your task is to calculate the total number of distinct ways this string of digits could be translated back into letters.
Constraints to Note:
- The string length is up to
100. - The string contains only digits
0-9. - The answer is guaranteed to fit in a 32-bit integer.
The Brute Force Approach
The naive approach is a recursive depth-first search. At each character, you try parsing just 1 digit, and then recursively decode the rest of the string. Then you try parsing 2 digits, and recursively decode the rest. This means each step branches into 2 possibilities, giving an O(2^N) time complexity. With N=100, 2^{100} is unfathomably large. The waste here is overlapping subproblems: if you decode "12" and are left with "345", and then you decode "1", then "2" and are left with "345", you evaluate "345" multiple times. We can cache this, or build it bottom-up.
The pattern
Same shape as 4.23.1 Climbing Stairs — at each position you consume one digit or two — but now each move has a condition.
Let dp[i] be the number of ways to decode the first i characters.
dp[i] = \underbrace{dp[i-1] \ \text{if the last digit is 1–9}}_{\text{take one digit}} \ + \ \underbrace{dp[i-2] \ \text{if the last two form 10–26}}_{\text{take two digits}}
Counting, so the operator is +.
The three rules that decide everything
The whole problem is the validity conditions, and each has an input designed to catch you.
A single digit is valid unless it is 0. There is no letter 0, so "0" alone decodes zero ways.
A pair is valid only between 10 and 26. That means the first digit must be 1 or 2, and if it is 2 the second must be at most 6.
A leading zero in a pair is invalid. "06" is not 6 — the pair must start with 1 or 2, so 0 never begins a valid two-digit code. This is the case that breaks naive solutions, and "06" is on the test set for exactly that reason.
The consequence worth stating: a 0 in the input can only ever be decoded as part of 10 or 20. Any other 0 makes the whole string undecodable, and the count collapses to zero and stays there.
The solution
python
class Solution:
def numDecodings(self, s: str) -> int:
if not s or s[0] == '0':
return 0
two_back, one_back = 1, 1 # dp[0] = 1 (empty), dp[1] = 1
for i in range(1, len(s)):
current = 0
if s[i] != '0': # take one digit
current += one_back
two_digit = int(s[i - 1: i + 1])
if 10 <= two_digit <= 26: # take two digits
current += two_back
two_back, one_back = one_back, current
return one_backts
function numDecodings(s: string): number {
if (!s || s[0] === '0') return 0;
let twoBack = 1, oneBack = 1;
for (let i = 1; i < s.length; i++) {
let current = 0;
if (s[i] !== '0') current += oneBack;
const twoDigit = Number(s.slice(i - 1, i + 1));
if (twoDigit >= 10 && twoDigit <= 26) current += twoBack;
twoBack = oneBack;
oneBack = current;
}
return oneBack;
}dp[0] = 1 is the base case that trips people up. The empty string has exactly one decoding — the empty one. It looks like it should be 0, but making it 1 is what allows a valid two-digit code at the very start to be counted: for "12", the pair 12 contributes dp[0] = 1, which is correct.
The s[0] == '0' guard rejects a string that cannot start at all.
current starts at 0 every iteration, so a position where neither move is legal correctly yields 0 — and from then on every later position sees a 0 and stays 0. The zero propagates by itself, which is exactly right.
10 <= two_digit <= 26 covers the leading-zero rule for free, because "06" is 6, which is below 10.
Trace
"226"
| i | char | one-digit? | two-digit | valid pair? | current |
|---|---|---|---|---|---|
| start | two_back = 1, one_back = 1 | ||||
| 1 | 2 | yes → +1 | 22 | yes → +1 | 2 |
| 2 | 6 | yes → +2 | 26 | yes → +1 | 3 |
Answer 3 ✓ — "BBF", "VF", "BZ".
Now "06": the guard fires on s[0] == '0' and returns 0 immediately.
And "106": at i = 1 the char is 0, so no one-digit move; the pair 10 is valid, so current = dp[0] = 1. At i = 2 the char is 6, so current = dp[1] = 1; the pair 06 is invalid. Answer 1 — "JF" ✓.
Complexity
O(n) time, O(1) space.
Time Complexity Derivation: We iterate through the string of N digits exactly once. Inside the loop, we are doing simple character checks and integer conversions on slices of length 2, which take O(1) time. Thus, the total time is strictly O(N).
Space Complexity Derivation: Although a full DP array would take O(N) space, we optimize it down to O(1) because dp[i] only relies on dp[i-1] and dp[i-2]. We just keep two variables (one_back and two_back), meaning the memory footprint remains constant regardless of the string length.
Where this goes next
- Decode Ways II — the input may contain
*, meaning any digit from 1 to 9. The same recurrence with counted possibilities instead of yes-or-no, and the arithmetic becomes fiddly. A good demonstration that the shape survives while the conditions get harder. - Climbing Stairs — this recurrence with no conditions at all. 4.23.1.
- Word Break — the same "can I split this string" idea, but the pieces can be any length and are checked against a dictionary. 4.23.10.
The family: split a string into valid pieces. Fixed piece lengths give this problem; arbitrary lengths give Word Break; palindromic pieces give Palindrome Partitioning. Same skeleton, different validity test.
What the interviewer will push on
"Why is dp[0] = 1?" The empty string has one decoding, and that base value is what lets a leading two-digit code be counted.
"What does '06' do?" Zero ways. The pair rule requires 10 to 26, so a leading zero can never form a valid pair.
"Where can a 0 legally appear?" Only as the second digit of 10 or 20.
"Walk through '2101'." A good test — the answer is 1, and it exercises both zero rules.
"O(1) space?" Two variables, since only the previous two values are read.
One thing to volunteer: enumerate the three validity rules before writing code, and name the input that breaks each. This problem is not hard once the rules are written down; it is hard when you discover them one failing test at a time.
Next: 4.23.8 Coin Change — the classic optimisation DP, and the clearest proof that greedy fails.