Recursion & DP Target: 15s
Like climbing stairs but with validity checks. Single digit (1-9) adds dp[i-1], two digits (10-26) adds dp[i-2].
def numDecodings(s):
if not s or s[0] == '0':
return 0
n = len(s)
dp = [0] * (n + 1)
dp[0] = dp[1] = 1
for i in range(2, n + 1):
if s[i-1] != '0':
dp[i] += dp[i-1]
two = int(s[i-2:i])
if 10 <= two <= 26:
dp[i] += dp[i-2]
return dp[n]Type it from memory. Go.