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.
Top comments (0)