# Time Limit Exceeded - why????

• Probably using "dict" is inefficient!

``````class Solution(object):
def numDecodings(self, s):
"""
:type s: str
:rtype: int
"""

dic = dict()
dic['0'] = 0   # '0' can be 0
for i in range(1,27):
dic[str(i)] = 1 # for numbers in range '1' to '26'

dic['*']  = 9  # *  - 1 - 9
dic['1*'] = 9  # 1* - 11 - 19 (9)
dic['2*'] = 6  # 2* - 21 - 26 (6)
dic['**'] = 15 # ** - 15 (add above two)

# '*0' to '*6' - * can be 1 or 2
for i in range(0,7):
dic['*' + str(i)] = 2

# '*7' to '*9' - * can only be 1
for i in range(7,10):
dic['*' + str(i) ] = 1

if s == None or len(s) == 0:
return 0

n    = len(s)
f0   = f1 = f2 = 0
f0   = f1 = f2 = dic.get(s[0],0)

if n > 1: # if at least 2 chars are present
f2 = f1 = f0*dic.get(s[1],0) + dic.get(s[0:2],0) # how many ways can you decode first couple

if n > 2:
f2 = f1*dic.get(s[2],0) + f0*dic.get(s[1:3],0)

for i in range(3,n):
f1 = f2
f2 = f1*dic.get(s[i],0) + f0*dic.get(s[i-1:i+1],0)

return f2 % (10**9 + 7)``````

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