Learning On the Way

282. Expression Add Operators

Given a string num that contains only digits and an integer target, return all possibilities to insert the binary operators '+', '-', and/or '*' between the digits of num so that the resultant expression evaluates to the target value.

Note that operands in the returned expressions should not contain leading zeros.

class Solution: 
    def addOperators(self, num, target): 
        self.res, self.target = [], target 
        self.num = num 
        self.N = len(self.num) 
        for i in range(1, len(num)+1): 
            if i == 1 or (i > 1 and num[0] != "0"): # prevent "00*" as a number 
                self.dfs(i, num[:i], int(num[:i]), int(num[:i])) # this step put first number in the string 
        return self.res 
    def dfs(self, idx, exp, cur, last): 
        N = self.N 
        if idx == N: 
            if cur == self.target: 
                self.res.append(exp) 
            return 
        for i in range(idx + 1, N + 1): 
            s = self.num[idx:i] 
            val = int(s) 
            if i == idx + 1 or (i > idx + 1 and self.num[idx] != "0"): # prevent "00*" as a number 
                self.dfs(i, exp + "+" + s, cur + val, val) 
                self.dfs(i, exp + "-" + s, cur - val, -val) 
                self.dfs(i, exp + "*" + s, cur - last + last * val, last * val)