Why is my Python Code too slow?


  • 0
    J

    Why I'm I receiving a Time Limit Exceeded error. For the most part, it looks like my code performs in linear time, which is the actual running time of this program. If it is performing in this time, then why I'm getting this error.

    class Solution:
        # @param {string} s
        # @return {integer}
        stuff = ["(", ")"]
        def evaluate(self, stack):
            while True and len(stack) >=3:
                if stack[2] == "(" and stack[0]==")":
                    stack.pop(2)
                    stack.pop(0)# remove parenthesis
                elif stack[1] =="-"and all(not parenthesis in self.stuff for parenthesis in [stack[0], stack[2]]):
                    value = int(stack[2]) - int(stack[0])
                    [stack.pop(0) for i in range(3)] #pop the stack 3 times]
                    stack.insert(0,value)
                elif stack[1] =="+" and all(not parenthesis in self.stuff for parenthesis in [stack[0], stack[2]]):
                    value = int(stack[2]) + int(stack[0])
                    [stack.pop(0) for i in range(3)] #pop the stack 3 times
                    stack.insert(0,value)
                else:
                    return
    
    
    
        def calculate(self, s):
            stack = []
            #use regex
            s = re.sub(r'\s+', '', s)
            s=re.split(r'([\+\-\(\)])', s)
            s=[x for x in s if x] #remove empty strings
    
            while len(s) > 0 or len(stack) >1:
                if len(s)>0:
                    stack.insert(0, s.pop(0))
                self.evaluate(stack)#u evaluate
    
    
            return stack[0]

  • 0

    insert(0, ...) and pop(0) take linear time every time because the whole contents have to be shifted. Better work at the end of the list, where they only take constant time. Or go through it with an index. I didn't think through evaluate, but the repeated s.pop(0) in calculate alone will likely cause you to exceed the time limit.


Log in to reply
 

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