Python solution with detailed explanation

  • 0


    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]))
                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"
                    if k == 0:
                        self.helper(i+1, num, ileft, ileft, left, t, res)
                        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)

Log in to reply

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