# Simple Python DP Solution

• ``````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[i-1]
t = int(test)

if not t % 10 :
if not t or t / 10 >= 3:
return 0
else :
dp[i] = dp[i-2]
elif t > 26 or t < 10:
dp[i] = dp[i-1]

else : dp[i] = dp[i-1] + dp[i-2]

return dp[-1]``````

• This uses `O(n)` memory for `dp` but since we only look back that last two entries in `dp`, 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[i-2: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]
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.