Time Limit Exceeded - why????


  • 0
    S

    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)

Log in to reply
 

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