Decode Ways
Count the ways to decode a digit string where 1-26 map to A-Z.
- 1 <= s.length <= 100
- s contains only digits and may contain leading zero(s).
Intuition
Decode ways counts how many ways a digit string maps back to letters, where A is 1 through Z is 26. The count grows like Fibonacci, and the reason is visible in the recurrence.
At each position, a decoding either takes one digit or two. So the number of ways to decode the string up to position i is the ways up to i−1 (if the single digit is valid) plus the ways up to i−2 (if the two-digit pair is valid):
- dp[i] = dp[i-1] + dp[i-2], with each term included only when that digit or pair actually decodes.
That structure is Fibonacci with validity conditions, and those conditions are where the problem's difficulty lives.
A zero cannot stand alone. '0' maps to no letter, so a single digit is valid only when it is 1 through 9. A string containing 0 decodes only if that zero pairs with the digit before it, as in 10 or 20.
A pair must fall between 10 and 26. Both bounds matter — 27 exceeds Z, and 06 is not a valid two-digit code because leading zeros are not permitted. Checking only the upper bound wrongly accepts 06.
The base case dp[0] = 1 represents the empty string having exactly one decoding, which makes dp[2] correct for valid two-digit inputs.
A leading '0' makes the whole string undecodable, returning 0. Since only the previous two values are ever needed, the array collapses to two variables and O(1) space.
Climbing Stairs with validity conditions on each step. From position i you may take one digit (if it isn't '0') or two (if they read 10–26). Zeros are the whole difficulty: '0' can never stand alone, so it only survives as the second half of a 10 or 20.
Approach
Before reading on: price up what the direct approach costs here, then ask what a single cell should mean, and which earlier cells it needs. Aim for O(n) time and O(n), or O(1) with rolling variables space.
See the two choices per position
A decoding takes either one digit or two, so the ways to reach position i come from i-1 and i-2. This is Fibonacci with validity conditions attached.
Set the base cases
dp[0] = 1 — the empty string has exactly one decoding. This seeming technicality is what makes two-digit inputs come out right.
Validate the single digit
Add dp[i-1] only when the current digit is 1 through 9. A 0 cannot stand alone, since it maps to no letter.
Validate the two-digit pair
Add dp[i-2] only when the pair is between 10 and 26. Both bounds matter — 27 exceeds Z, and 06 is invalid because leading zeros are not permitted.
Return zero for a leading zero
A string starting with '0' has no valid decoding. Detecting this immediately avoids propagating zeros through the whole table.
Collapse to two variables
Only the previous two values are ever read, so the array reduces to two rolling variables — O(1) space with no change to the logic.
Cost of the scan
One pass with constant work per character gives O(n) time and O(1) space after the rolling-variable optimisation.
Solution & live demo
Common pitfalls
Allowing '0' as a single digit
dp[i] += dp[i - 1]
if one_digit != '0':
dp[i] += dp[i - 1]No letter maps to 0, so a standalone zero decodes to nothing and that path must contribute zero ways. Without the guard, strings like "100" report decodings that don't exist.
Accepting two-digit values below 10
if two_digit <= 26:
if 10 <= two_digit <= 26:
"06" is not a valid encoding of 6 — leading zeros aren't allowed. Testing only the upper bound admits every "0X" pair and inflates the count.
Seeding dp[1] unconditionally
dp[1] = 1
dp[1] = 1 if s[0] != '0' else 0
A string starting with '0' has no valid decoding at all, and that zero must propagate from the very first position. Seeding 1 lets an impossible prefix contribute ways to every later position.
Edge cases
dp[1] = 0 immediately, and that zero propagates forward, correctly producing 0 total decodings.
The single digit check fails for '0', so only the pair (must be '10' or '20') can supply a decoding; anything else collapses to 0.
The two-digit branch is skipped since 27 > 26; only the single-digit branch (if valid) contributes.
Loop never runs; the answer is just dp[1], which is 1 unless that character is '0'.