Python solution with detailed explanation


  • 0
    G

    Solution

    Expression Add Operators https://leetcode.com/problems/expression-add-operators/

    Recursion and Backtracking

    1. Make sure you understand the problem: 1234 does not mean adding brackets, we just need to add operators.
    2. 1234 = Processed "12" and now handle the substring "34".
    3. We could have processed "12" in many ways. But when we reach the part of "34", we just care about the value computed so far and the immediate prev value.
    4. For example: "1+2", "1-2", "1*2" would have a so_far value as 3,-1,2 and previous value as 2,-2,2.
    5. When we reach "34", we would have arrived from one of the paths like "1+2", "1-2", "1*2". We therefore know the prev value. This is needed for multiplication part since (1+2)*3 should be really 1+2*3 since we dont have any brackets. Hence we do 1+2-2+2*3
    class Solution(object):
        def addOperators(self, num, target):
            """
            :type num: str
            :type target: int
            :rtype: List[str]
            """
            results = []
            self.helper(0, num, 0, 0, "", target, results)
            return results
        
        def helper(self, k, num, ssum, prev, e, t, res):
            if k == len(num):
                if ssum == t:
                    res.append("".join([x for x in e]))
            else:
                for i in range(k, len(num)):
                    left = num[k:i+1]
                    ileft = int(left)
                    if left[0] == "0" and len(left) > 1: ### IGNORE INPUT LIKE "00", "005", "0006"
                        continue
                    if k == 0:
                        self.helper(i+1, num, ileft, ileft, left, t, res)
                    else:
                        self.helper(i+1, num, ssum+ileft, ileft, e+"+"+left, t, res)
                        self.helper(i+1, num, ssum-ileft, ileft*-1, e+"-"+left, t, res)
                        self.helper(i+1, num, ssum-prev+ileft*prev, ileft*prev, e+"*"+left, t, res)
                return
    

Log in to reply
 

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