282. Expression Add Operators

https://leetcode.com/problems/expression-add-operators/

题目解释

题目会给一组全部都是数字的字串，还有一个数字target ，请用+、-、*组出能得到target的算式，并回传所有可能结果

example

解法

今天的题目一看就知道要用backtracking，但我还是写不出来就是了

所以今天我就来分享看懂解答的过程，所以先上程序码吧

程序码

class Solution:
    def addOperators(self, num: str, target: int) -> List[str]:
        
        def backtracking(index, prev, curr, n, path):

            if index == len(num):
                
                if target == n and curr == 0:
                    ans.append(''.join(path[1:]))
                return 
            
            curr = curr * 10 + int(num[index])
            
            if curr > 0: #一大坨东西
                backtracking(index+1, prev, curr, n, path)
            
            # 加
            backtracking(index+1, curr, 0, n + curr, path + ['+', str(curr)])

            if path:
                #减
                backtracking(index+1, -curr, 0, n - curr, path + ['-', str(curr)])
                
                #乘
                backtracking(index+1, prev * curr, 0, n - prev + prev * curr, path + ['*', str(curr)])

            
        
        ans = []
        backtracking(0, 0, 0, 0, [])
        
        return ans

那我们就重头开始吧!

1. 首先，我们先定义一个backtracking 函数，里面5个参数代表目前字串位置、前一个数字、现在数字、算式累积结果、目前的算式

def backtracking(index, prev, curr, n, path)

2. backtracking都会有个中断条件，要嘛发现不能做了，要嘛做完大功告成

而这题的结束且有结果的条件有3个:

• 我们的指标已经到尾端了
• 我们手上的东西都处理完了
• 算式的结果符合题目要求

if index == len(num):

    if target == n and curr == 0:
        ans.append(''.join(path[1:]))
    return 

3. 接着，我们先来看现在数字的计算

curr = curr * 10 + int(num[index])

算式里的curr * 10是因为字串里的数字不只能当成个位数，也能组成二位数、三位数...

如果curr = 0的话，就是把数字当个位数处理

4. 这部分就是专门处理组合多位数的，要求大於0的原因我觉得很难讲，只能请大家印出来自行体会

if curr > 0: #一大坨东西
    backtracking(index+1, prev, curr, n, path)

5. 接着，我们看相加的部分

backtracking(index+1, curr, 0, n + curr, path + ['+', str(curr)])

prev的栏位放curr是因为我们目前的数字对下个backtracking的数字来说是先前数字；curr的栏位放0则可以当成是一个新开始的算式；累积的结果加上去就好

6. 相减的部分也差不多，不过在那之前有个if path的判断式，可以想成是要有东西可以减才成执行

backtracking(index+1, -curr, 0, n - curr, path + ['-', str(curr)])

7. 乘法看起来比较不一样，在累积结果的部分出现减法是因为乘号的优先度较高，感觉如下面这张图
   
   backtracking(index+1, prev * curr, 0, n - prev + prev * curr, path + ['*', str(curr)])

8. 连我自己都看不懂我在打什麽了，建议还是自己动手拿纸笔模拟一遍好了

闲聊

今天的题目是这个月第一次用到回朔法，结果就直接来hard题目了

如果有人和我一样想不出来只能看解答的

看完後可以试解这题来看看自己是否已理解解答