A tricky DP problem where the base cases are the hardest part — zeros break everything.
A message is encoded as a number string where A=1, B=2, ..., Z=26. Given an encoded string, return the number of ways to decode it.
# "12" → 2 ways: "AB" (1,2) or "L" (12)
# "226"→ 3 ways: "BZ" (2,26), "VF" (22,6), "BBF" (2,2,6)
# "06" → 0 ways: no letter maps to 0 or 06At each position i, there are two choices:
s[i] — valid if it's 1–9 (not '0'). Adds dp[i-1] ways.s[i-1:i+1] — valid if it's 10–26. Adds dp[i-2] ways.dp[i] = total valid decodings of the first i characters.
def num_decodings(s):
if not s or s[0] == '0':
return 0
n = len(s)
dp = [0] * (n + 1)
dp[0] = 1 # empty string: 1 way to decode
dp[1] = 1 # first char: 1 way (we checked it's not '0')
for i in range(2, n + 1):
one_digit = int(s[i - 1])
two_digit = int(s[i - 2:i])
if 1 <= one_digit <= 9:
dp[i] += dp[i - 1]
if 10 <= two_digit <= 26:
dp[i] += dp[i - 2]
return dp[n]
print(num_decodings("12")) # 2
print(num_decodings("226")) # 3
print(num_decodings("06")) # 0| i | one_digit | two_digit | dp[i] | Reasoning |
|---|---|---|---|---|
| 0 | — | — | 1 | Base: empty string |
| 1 | — | — | 1 | Base: "2" has 1 decoding |
| 2 | 2 (valid 1–9) | 22 (valid 10–26) | 2 | dp[1] + dp[0] = 1+1 |
| 3 | 6 (valid 1–9) | 26 (valid 10–26) | 3 | dp[2] + dp[1] = 2+1 |
Answer: dp[3] = 3 ✓
print(num_decodings("10")) # 1 ("J"=10, can't decode as 1+0)
print(num_decodings("100")) # 0 (no way to decode — "100" has no valid split)
print(num_decodings("2101")) # 1 ("U"+"A" = 21,0,1 — only 10+1="JA" → but 21=U, 01 invalid)10 ≤ two_digit ≤ 26 handles this correctly.dp[i] depends on dp[i-1] and dp[i-2] — but with conditional additions based on validity. You can space-optimize to O(1) using two rolling variables exactly like Climbing Stairs.