Given a string that contains only digits0-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. Take2+3*2
as an example, when we process2+3
, we get5
. When we meet the*
, we cannot multiply5
with2
. The trick here is that we can remember the previous value3
.
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