Leetcode 282: Expression Add Operators

Expression Add Operators

https://leetcode.com/problems/expression-add-operators/

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

Examples:

"123", 6 -> ["1+2+3", "1*2*3"] 
"232", 8 -> ["2*3+2", "2+3*2"]
"00", 0 -> ["0+0", "0-0", "0*0"]
"3456237490", 9191 -> []

 

Code:

class Solution(object):
    def addOperators(self, num, target):
        """
        :type num: str
        :type target: int
        :rtype: List[str]
        """
        def solve(target, pos, negate, prod):
            expr = []

            for i in xrange(pos, len(num)):
                if i != pos and num[pos] == "0":
                    break

                if i == len(num) -1:
                    if negate * prod * int(num[pos:i+1]) == target:
                        expr.extend([num[pos:i+1]])
                    break
                
                add_expr = solve(target - prod * negate * long(num[pos:i+1]), i+1, 1, 1)
                expr.extend([num[pos:i+1] + "+" + e for e in add_expr])

                sub_expr = solve(target - prod * negate * long(num[pos:i+1]), i+1, -1, 1)     
                expr.extend([num[pos:i+1] + "-" + e for e in sub_expr])

                mul_expr = solve(target, i+1, 1, prod * negate * long(num[pos:i+1]))
                expr.extend([num[pos:i+1] + "*" + e for e in mul_expr])

            return expr
        
        return solve(target, 0, 1, 1)

 

Idea:

Overall we use recursion (DFS) to solve this problem. 

We need to determine where to put the first operator. Operators can be added randomly among digits. For example, output expressions can contain multi-digits number such as `12 + 123* 0`. That is why we need `for i in xrange(pos, len(num)):` in line `11` to try out all possible positions to insert the first operator.

Then we need to avoid to put invalid numbers in the expression which start with “0”. That is done by line `12` to `13`.

The main part is `solve` function. It records the current position we are looking at (`pos`), whether the previous operation is minus (`negate`) and a product of previous numbers if the previous operation is product (`prod`).  The process is to try different operators and numbers, and to evaluate the current expression being tried.

 

If the next operation after the first number (A) is `+`, for example:

A+B*C = target

A+B+C = target

then we can equivalently try to solve (B C) with target=target-A. But we need to consider A if any operator before it is minus or multiple. That’s why we should rather reframe target = target – prod * negate * A.

 

If the next operation after the first number (A) is `-`, for example,

A – B*C = target

A – B+C = target

then we can equivalently try to solve(-B C) with target=target-A. Here we negate B by letting negate=-1 in the `solve `function.

 

If the next operation after the first number (A) is `*`, for example,

A*B*C = target

A*B+C = target

then we need to record the A as the current accumulated product.