Intuition
It is tempting to treat this like Climbing Stairs and always add dp[i-1] and dp[i-2], but here each contribution is conditional. dp[i-1] only counts if the current digit is not '0' (a lone '0' has no letter). dp[i-2] only counts if the two-digit number it forms is between 10 and 26 (so '06' is not a valid pair either, since a decoded letter never has a leading zero). Skip a check and you either overcount impossible splits or undercount valid ones. The fix is to test both conditions independently at every position and add only the branches that pass. The invariant: dp[i] is the number of ways to decode the first i characters, built from at most two valid predecessors.
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
Base cases
dp[0] = 1 represents the empty prefix, which has exactly one (trivial) decoding. dp[1] is 1 if the first character is not '0', else 0, since a leading zero can never be decoded alone.
Conditional transition
For each position i from 2 to n, look at the single digit s[i-1] and the pair s[i-2:i]. Add dp[i-1] only if the single digit is not '0'. Add dp[i-2] only if the pair's numeric value is between 10 and 26. dp[i] is the sum of whichever of those apply; if neither applies, dp[i] is 0 and that branch is dead.
Final answer
dp[n] holds the total number of ways to decode the whole string. Because each step only reads the previous two entries, the array can be collapsed to two rolling variables for O(1) space.
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'.