# Python AC with 68ms

• Could make the code more clean?

``````class Solution:
def __init__(self):
self.d = {}
# @param s, a string
# @return an integer
def numDecodings(self, s):
def num2(s):
t = int(s)
if t == 10 or t == 20 : return 1
if t>10 and t<27: return 2
elif t>=0 and t<10: return 0
elif s[1]=='0': return 0
else: return 1
len_= len(s)
if len_ == 0 or s[0] == '0' : return 0
if len_ == 1 : return 1
if len_ == 2 : return num2(s)
tmp = s[-2:]
t = num2(tmp)
if not self.d.has_key(len_-2): self.d[len_-2] = self.numDecodings(s[:-2])
if not self.d.has_key(len_-1): self.d[len_-1] = self.numDecodings(s[:-1])
if t == 1 :
if tmp[1] == '0': return self.d[len_-2]
return self.d[len_-1]
elif t == 2:
return self.d[len_-2] + self.d[len_-1]
else:
if tmp[1] == "0": return 0
else: return self.d[len_-1]``````

• ``````class Solution:
# @param s, a string
# @return an integer
def numDecodings(self, s):
if s[0:1]=='0' or len(s) == 0:
return 0
res = list()
sum = 1
count = 0
max = 0
i = 1
length = len(s)
while i<length:
if s[i-1:i]=='0':
return 0
t = int(s[i-1:i+1])
if s[i:i+1]!='0' and t >= 10 and t <= 26:
count += 1
elif s[i:i+1]=='0':
if t==10 or t==20:
if count != 0:
res.append(count)
if count > max:
max = count
count = 0
if i+2 <= length:
if s[i+1:i+2]=='0':
return 0
i += 1
else:
return 0
else:
if count != 0:
res.append(count+1)
if count+1 > max:
max = count+1
count = 0
i += 1
if count != 0:
res.append(count+1)
if count+1 > max:
max = count+1
fab = [None]*(max + 3)
fab[1] = 1
fab[2] = 2
if max > 2:
for i in range(3,max+1):
fab[i] = fab[i-1] + fab[i-2]
for x in res:
sum *= fab[x]
return sum
``````

`52ms`

• It`s Fabonacci Number in fact.

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