def numDecodings(self, s):
if not s or not int(s[0]) : return 0
dp = [1 for i in range(len(s)+1)]
test = s[0]
for i in range(2, len(s)+1) :
test = test[1] + s[i1]
t = int(test)
if not t % 10 :
if not t or t / 10 >= 3:
return 0
else :
dp[i] = dp[i2]
elif t > 26 or t < 10:
dp[i] = dp[i1]
else : dp[i] = dp[i1] + dp[i2]
return dp[1]
Simple Python DP Solution


This uses
O(n)
memory fordp
but since we only look back that last two entries indp
, we can change this to use constant memory.class Solution(object): def numDecodings(self, s): """ :type s: str :rtype: int """ if not s or s[0] == '0': return 0 dp = [1, 1] for i in range(2, len(s)+1) : num = int(s[i2:i]) if num % 10 == 0: if num == 0 or num > 20: # hit a snag like 00, 30, 40, *0 return 0 else: # num is 10 or 20, must take double v = dp[2] elif num > 26 or num < 10: # num has to be taken as a single v = dp[1] else: # num can be a single or a double v = dp[1] + dp[2] dp.append(v) dp.pop(0) return dp[1]