The time limitation of python code is unreasonable


  • 0
    M

    it only less than 1s on my macbook to run this case "2147483647", 2147483647.

    But it leads to a Time Limit Exceeded when I try to judge it online.

    I've tried my best to optimize my code and gear up the speed, but I failed in no reason.

    Frustrated. (sad face)

    enter image description here

    Here is my code:

    class Solution(object):
        def addOperators(self, nums, target):
            self.res = []
            self.visit = {}
            if nums:
                self.do_addOps(nums, target, '')
            return self.res
            
        def do_addOps(self, nums, target, expr):
            if not nums:
                res = self.myeval(expr)
                if res == target:
                    self.res.append(expr)
                return
            n = len(nums)
    
            self.do_addOps('', target, expr + nums)
    
            for i in xrange(1, n):
                a = nums[:i]
                b = nums[i:]
                
                for c in ['+', '-', '*']:
                    self.do_addOps(b, target, expr + a + c)
    
        def myeval(self, expr):
            if expr in self.visit:
                return self.visit[expr]
            for symbol, fun in [
                    ('*', lambda x, y: x * y), 
                    ('+', lambda x, y: x + y),
                    ('-', lambda x, y: x - y)]:
                idx = expr.find(symbol)
                if idx != -1:
                    res = fun(self.myeval(expr[:idx]), self.myeval(expr[idx + 1]))
                    self.visit[expr] = res
                    return res
    
            res = int(expr)
            self.visit[expr] = res
            return res
        
    S = Solution()
    print S.addOperators("2147483647", 2147483647)
    

Log in to reply
 

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