Python recursive and DP solution

• recursive - LTE even with cache - no go

``````class Solution:
# @param s, a string
# @return an integer
# 8:19
def numDecodings(self, s):
if s == '':
return 1

if s[0] == '0':
return 0

possibleDouble = True if self.isPossibleDouble(s[:2]) else False

if possibleDouble:
return self.numDecodings(s[1:]) + self.numDecodings(s[2:])
else:
return self.numDecodings(s[1:])

def isPossibleDouble(self, num):
return len(num) == 2 and (num[0] == '1' or (num[0] == '2' and num[1] <= '6'))
``````

DP

``````class Solution:
# @param s, a string
# @return an integer
def numDecodings(self, s):
if not s:
return 0

n = len(s)
dp = [0] * (n + 1)
dp[0] = 1

for i in range(1, n + 1):
if s[i-1] != '0':
dp[i] += dp[i-1]
if len(s[i-2:i]) == 2 and '10' <= s[i-2:i] <= '26':
dp[i] += dp[i-2]

return dp[n]``````

• I had doubt about the recursive so I copy past it and it fails the test case without reaching an LTE. Either the tests have change or it do not works.

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