[Leetcode]282. Expression Add Operators

Given a string that contains only digits 0-9 and a target value, return all possibilities to add binaryoperators (not unary) +, -, or * between the digits so they evaluate to the target value.

Initially, I adopted the strategy of using DFS to generate all possible strings containing digits and operators, and then evaluating each of them. However, this only made it super complicated. @czonzhu provides a clear and clean solution – we can do the generating strings and calculating values at the same time.

Here are several edge cases we need to deal with along with our DFS:

At the beginning, we cannot put operators before the first digit.
We cannot have numbers with leading zeros.
When we put a *, we cannot multiply the coming number to the original value. Take 2+3*2 as an example, when we process 2+3, we get 5. When we meet the *, we cannot multiply 5 with 2. The trick here is that we can remember the previous value 3.

Code

Comments are inserted to explaining how the edge cases get covered.

class Solution:
    def addOperators(self, num: str, target: int) -> List[str]:
        n,ret = len(num),[]
        if n == 0: return []
        def helper(ind,path,cnt,prev):
            if ind == n:
                if cnt == target: ret.append(path)
                return
            for i in range(ind,n):
                # make sure do no generate numbers with leading zeros
                if i != ind and num[ind] == '0': break 
                # cover cases when there is no operator between digits
                cur = int(num[ind:i+1])
                # do not put operators at the begining
                if ind == 0:
                    helper(i+1,path+num[ind:i+1],cnt+cur,cur)
                # record the previous value
                else:
                    helper(i+1,path+'+'+num[ind:i+1],cnt+cur,cur)
                    helper(i+1,path+'-'+num[ind:i+1],cnt-cur,-cur)
                    helper(i+1,path+'*'+num[ind:i+1],cnt-prev+prev*cur,prev*cur)
        helper(0,'',0,0)
        return ret

Code

Reference

Related posts: