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]
```