Leetcode 282: Expression Add Operators
Tags: algorithms, leetcode, grind
Published: 2021-08-13 23:04:04

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.

```python
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.

```python
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.