Given a string that contains only digits
0-9and a target value, return all possibilities to add binaryoperators (not unary)
*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*2as an example, when we process
2+3, we get
5. When we meet the
*, we cannot multiply
2. The trick here is that we can remember the previous value
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