Why TLE for Python code for input 30


  • 0
    S

    I am unable to figure out what's taking most time in this code for input 30.

    time python -m cProfile count_and_say.py
    37666 function calls in 0.218 seconds

    class Solution:
    def _countDict(self, mydict, value, prevValue):
        result = ''
        
        if (prevValue != -1) and (prevValue != value):
            result += "%d%d"%(mydict[prevValue], prevValue) 
            mydict = {}
            
        if mydict.has_key(value):
            mydict[value] += 1
        else:
            mydict[value] = 1
        
        return result, mydict
    
    def _countvalue(self, value):
        result = ''
        mydict = {}
        prevValue = -1 # keep track of last value within loop 
        while value /10 != 0:
            newresult, mydict = self._countDict(mydict, value % 10, prevValue)
            prevValue = value % 10
            value = value /10
            result +=newresult
    
        newresult, mydict = self._countDict(mydict, value, prevValue)
        result+=newresult
        if len(mydict) > 0:
            result+="%d%d"%(mydict[value], value)
        return int(result)
    
    # @return a string
    def countAndSay(self, n): # 1, 11, 21, 1211, 111221, 322211
        value = 1
        result = ''
        while (n > 0) and (value is not None):
            # print "Value: ", value
            value = self._countvalue(value)
            n -= 1
        return str(value)

Log in to reply
 

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