Iterative TLE - can improve?


  • 0
    Y

    I'm wondering if it's possible to improve this approach or only a recursive DFS will work?
    Between each digit of nums there are 4 possible operators: +, -, * and nothing.
    I enumerate all expressions where each operator is inserted into each position. There are 4**(len(nums)-1) of these possible expressions.
    Then each expression is evaluated to see if it is equal to target.
    One extra check ensures I don't have a leading '0' for an integer apart from zero itself.

    I think the advantage of dfs is that in reuses the evaluation of part of an expression, but here I create each full expression before evaluation it.

        def addOperators(self, num, target):
    
            if not num:
                return [] if target else ['0'] 
    
            expressions = []
            mapping = {0 : '', 1 : '*', 2 : '+', 3 : '-'}
            possibles = 4**(len(num)-1)
            
            for possible in range(possibles):
                expression = [num[0]]
    
                for c in num[1:]:
                    possible, operator = divmod(possible, 4)
                    if operator == 0 and expression[-1] == '0' and len(expression) > 1 and not expression[-2].isdigit():
                        break
                    expression.append(mapping[operator])
                    expression.append(c)
                else:      # if no break, evaluate expression
                    expression = ''.join(expression) 
                    if eval(expression) == target:
                        expressions.append(expression)
                        
            return expressions
    

Log in to reply
 

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