LeetCode #91 Medium

Decode Ways

Count the ways to decode a digit string where 1-26 map to A-Z.

dynamic-programmingstring

02

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.

03

Approach

1

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.

2

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.

3

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.

04

Solution & live demo

python

▶1class Solution:
▶2    def numDecodings(self, s: str) -> int:
▶3        n = len(s)
▶4        dp = [0] * (n + 1)
▶5        dp[0] = 1
▶6        dp[1] = 1 if s[0] != '0' else 0
▶7        for i in range(2, n + 1):
▶8            one_digit = s[i - 1]
▶9            two_digit = int(s[i - 2:i])
▶10            if one_digit != '0':
▶11                dp[i] += dp[i - 1]
▶12            if 10 <= two_digit <= 26:
▶13                dp[i] += dp[i - 2]
▶14        return dp[n]

05

Edge cases

String starts with '0'

dp[1] = 0 immediately, and that zero propagates forward, correctly producing 0 total decodings.

A '0' appears mid-string, e.g. '100'

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.

Pair exceeds 26, e.g. '27'

The two-digit branch is skipped since 27 > 26; only the single-digit branch (if valid) contributes.

Single character string

Loop never runs; the answer is just dp[1], which is 1 unless that character is '0'.

06

Complexity

Time

O(n)

Space

O(n), or O(1) with rolling variables

Single left-to-right pass over the string.