Given a string that contains only digits 0-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. Take 2+3*2 as an example, when we process 2+3, we get 5. When we meet the *, we cannot multiply 5 with 2. The trick here is that we can remember the previous value 3.

#### 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



Subscribe
Notify of