Use DFS but TLE


  • 1
    F

    I use DFS in my algorithm, just like many solutions. I use a queue to store all possible expansion and continue to expand until the queue is empty. In each element in the queue, there are an index pointing to the character in input number and a stack for representing current expression. The evaluate() function is used to evaluate the stack. I don't understand what is the difference between my algorithm and others, since I am clearly using DFS here.

    from collections import deque
    
    class Solution(object):
        def evaluate(self, opStack):
            stack = []
            #print "============"
            #print opStack
            idx = 0
            while idx < len(opStack):
                val = opStack[idx]
                if val == '-' or val == '+':
                    if len(stack) != 1:
                        temp1 = stack.pop()
                        op = stack.pop()
                        temp2 = stack.pop()
                        if op == '-':
                            stack.append(temp2-temp1)
                        else:
                            stack.append(temp1+temp2)
                    stack.append(val)
                elif val == '*':
                    temp1 = stack.pop()
                    stack.append(temp1*opStack[idx+1])
                    idx = idx + 1
                else:
                    # number
                    stack.append(val)
                idx = idx + 1
            
            if len(stack) != 1:
                temp1 = stack.pop()
                op = stack.pop()
                temp2 = stack.pop()
                if op == '-':
                    stack.append(temp2-temp1)
                else:
                    stack.append(temp1+temp2)
            #print stack[-1]
            return stack[-1]
            
        def addOperators(self, num, target):
            """
            :type num: str
            :type target: int
            :rtype: List[str]
            """
            if len(num) == 0:
                return []
                
            q = deque()
            if int(num[0]) != 0:
                q.append([1, [int(num[0])]]) # store the idx for next character and current operation stack
            q.append([1, [int(num[0]), '*']])
            q.append([1, [int(num[0]), '+']])
            q.append([1, [int(num[0]), '-']])
            
            ret = []
            
            while len(q) != 0:
                temp = q.popleft()
                stack = temp[1]
                if temp[0] == len(num):
                    val = self.evaluate(stack)
                    if val == target:
                        ans = ''.join( str(e) for e in stack )
                        ret.append(ans)
                elif stack[-1] == '*' or stack[-1] == '+' or stack[-1] == '-':
                    if temp[0]+1 != len(num):
                        newStack = stack + [int(num[temp[0]]), '*']
                        q.append([temp[0]+1, newStack])
                        newStack = stack + [int(num[temp[0]]), '+']
                        q.append([temp[0]+1, newStack])
                        newStack = stack + [int(num[temp[0]]), '-']
                        q.append([temp[0]+1, newStack])
                    if int(num[temp[0]]) != 0:
                        newStack = stack + [int(num[temp[0]])]
                        q.append([temp[0]+1, newStack])
                else:
                    # top of stack is a number
                    newNum = stack[-1]*10 + int(num[temp[0]])
                    stack.pop()
                    stack.append( newNum )
                    
                    q.append([temp[0]+1, stack])
                    if temp[0]+1 != len(num):
                        newStack = stack + ['*']
                        q.append([temp[0]+1, newStack])
                        newStack = stack + ['+']
                        q.append([temp[0]+1, newStack])
                        newStack = stack + ['-']
                        q.append([temp[0]+1, newStack])
                
            return ret
    

Log in to reply
 

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