Medium Tabulation Dynamic Programming
In plain English: Count how many valid letter-decodings a string of digits can have, where 1-26 each map to A-Z.
At each position, you can decode one digit (1-9) or two digits (10-26). dp[i] = dp[i-1] (one digit) + dp[i-2] (two digits) when valid.
Prompt
Given a string of digits, count the number of ways to decode it into letters (A=1, B=2, ..., Z=26).
Try to write it from scratch before scrolling down.
Solution
def num_decodings(s):
if not s or s[0] == '0':
return 0
n = len(s)
prev2, prev1 = 1, 1 # dp[0], dp[1]
for i in range(1, n):
cur = 0
if s[i] != '0':
cur += prev1 # single digit decode
two = int(s[i - 1:i + 1])
if 10 <= two <= 26:
cur += prev2 # two digit decode
prev2, prev1 = prev1, cur
return prev1
# Test: num_decodings("12") == 2 ("AB" or "L")
# Test: num_decodings("226") == 3 ("BZ", "VF", "BBF")
# Test: num_decodings("06") == 0