DFS solution in Python with more explanation


  • 0
    L
    def addOperators(self, num, target):
        """
        :type num: str
        :type target: int
        :rtype: List[str]
        """
    
        def dfs(num, start, left_total, last, target, single, result):
            if start == len(num):
                if left_total == target: # condition to get a solution
                    result.append(single)
            for i in range(start, len(num)):
                if i > start and int(num[start:i]) == 0:
                    start += 1
                    break
                val = int(num[start:i+1])
                dfs(num, i + 1, left_total + val, val, target, single + "+" + num[start:i+1], result)
                dfs(num, i + 1, left_total - val, -val, target, single + "-" + num[start:i+1], result)
                # back out the last val from left and get newly multiplied val*last and add it back to the left_total
                dfs(num, i + 1, left_total - last + last * val, last * val, target, single + "*" + num[start:i+1], result)
            
        result = []
        start = 0
        # you need this separate for loop for special handling the first operand.
        for i in range(start, len(num)):
            if i > 0 and int(num[:i+1]) == 0:
                start += 1
                break
            val = int(num[:i+1])
            dfs(num, i + 1, val, val, target, num[:i+1], result)
        return result

Log in to reply
 

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