Leetcode 282: Expression Add Operators

This one threw me off. The solution was conceptually kinda clear, but implementing it was a bit tricky.

So the input consists of a string num and an integer target. The string consists of digits, and the goal is to find all the ways to insert +,-,* operators to reach the target.

How to solve this is kinda clear. There isn't a way to be smart about things, so we'll just stick in the operators in all possible ways and see what we get. But how to actually code it? Here's a first attempt.

class Solution:
    def addOperators(self, num: str, target: int) -> List[str]:
        """
        scan num
        at each index in num you can either stick in an operator, or not
        exhaust all possibilities

        we will use recursion
        """
        def helper(prev: str, i: int):
            # it's often easier to have a helper function to perform the recursion
            # at the very least it should have the position i as an argument
            # and also whatever the previous string was cooked up (ie with inclusion of operators)
            if i == len(num):
                # check if prev is as solution
                if is_sol(prev):
                    ans.append(prev)

            else:
                # if we haven't reached the end, keep building the string
                for c in ['+','-','*','']:
                    helper(prev+c+num[i],i)

        ans = []
        helper('',0)
        return ans

This was actually pretty simple, but we still haven't implemented the is_sol function. How to do that? I think the easiest way is to use possibly the worst coding practice out there: eval. This is bad for two reasons: it's slow, and in a real system it would be an immense vulnerability. But this is leetcode, so we don't care. We'll just replace is_sol(prev) with eval(prev) == target.

However, we are not done. If you try to run that code, at least two issues may come up. The first is that we may be forming numbers from strings like 007, ie with leading zeros. The second is that we may be concatenating operators together, such as ** or +*. This is bad. We need to fix this. We just need to include some boring checks at the beginning.

class Solution:
    def addOperators(self, num: str, target: int) -> List[str]:
        """
        at each index in num you can either add in an operator or not
        the goal is to exhaust all possibilities

        can recurse over it
        """
        def helper(prev,i):
            # check if we can add num[i] to prev
            if len(prev) == 0:
                add_num = True
            elif prev[-1] in operators:
                add_num = True
            elif len(prev) == 1:
                if prev[-1] == '0':
                    add_num = False
                else:
                    add_num = True
            elif prev[-1] == '0' and prev[-2] in operators:
                add_num = False
            else:
                add_num = True
            # check if we can add operators and num[i] to prev
            if len(prev) == 0:
                add_ops = False
            elif prev[-1] in operators:
                add_ops = False
            else:
                add_ops = True

            if i == len(num):
                if eval(prev) == target:
                    ans.append(prev)
            else:
                if add_num:
                    helper(prev+num[i],i+1)
                if add_ops:
                    for c in operators:
                        helper(prev+c+num[i],i+1)

        operators = ['+','-','*'] 
        ans = []
        helper('',0)
        return ans

This was not pretty.

Blog

Leetcode 282: Expression Add Operators

John Calabrese

Join Our Newsletter. No Spam, Only the good stuff.

Related