[282][困难][回溯] 给表达式添加运算符

题目描述

给定一个仅包含数字 0-9 的字符串和一个目标值，在数字之间添加 二元 运算符（不是一元）+、- 或 * ，返回所有能够得到目标值的表达式。

示例 1:

输入: num = "123", target = 6
输出: ["1+2+3", "1*2*3"]

示例 2:

输入: num = "232", target = 8
输出: ["2*3+2", "2+3*2"]

示例 3:

输入: num = "105", target = 5
输出: ["1*0+5","10-5"]

示例 4:

输入: num = "00", target = 0
输出: ["0+0", "0-0", "0*0"]

示例 5:

输入: num = "3456237490", target = 9191
输出: []

提示：

• 0 <= num.length <= 10

• num 仅含数字

解题思路

容易想到本题解法的基本形式, 是按顺序遍历一个个数字, 然后尝试+, -, *的任意一种, 计算结果, 继续向下寻找数字. 因此需要使用DFS进行递归搜索.

首先在遍历确定数字时, 如果得到的数字是运算符前面的数字, 在DFS递归时就需要依次带着三种运算符进入到下一层, 而如果当前选择的符号是加减号, 而之后紧邻的一个运算符是乘号, 下次的递归就可以影响本次递归, 从而发散.

与计算器的题目[227][中等][栈] 基本计算器 II类似, 由于*的存在, 运算符存在优先级, 我们确定的数字, 其实是在确定运算符后面的数字. 因为确定完运算符后面的数字之后, 就可以对最后的运算符遍历穷举计算了, 并且时刻记录着前一个数字, 在遇到乘号时, 也能够方便的回溯, 重新计算更正当前结果.

具体来说, 在递归时, 我们需要维护几个变量:

• current_index: 当前数字的起始位置

• current_res: 当前表达式计算结果

• path: 当前表达式

• pre_num: 前一个数字

path与current_res是对应的. 在寻找新的数字时, 遍历从current_index开始一直遍历到原数字字符串的最后一个字符, 确定下新的数字后, 就可以枚举三种运算符, 与之前已经生成的表达式path结合, 更新结果current_res, 并得到新的path. 三种运算符对应着三种情况:

• +: 直接与之前的表达式结合, current_res直接加上当前数字得到新表达式的值

• -: 直接与之前的表达式结合, current_res直接减掉当前数字得到新表达式的值

• *: 由于乘法的优先级更高, 之前最后一个数字pre_num需要优先与当前产生的新数字计算, 而之前表达式current_res中已经包含了pre_num, 因此current_res需要先抵消掉pre_num, 然后再加上pre_num与当前数字相乘的结果, 作为新的current_res. 这里用了回溯的思路

因此前一个数字pre_num的更新起着至关重要的作用. 枚举三种可能的运算符, 计算得到新的表达式结果之后, 需要准备下一步递归, 当前数字也就成了下一步运算的pre_num. pre_num的更新也于当前步选择的运算符有关. 记当前数字为new_num:

• +: pre_num更新为new_num

• -: pre_num更新为-new_num

• *: 上面计算的过程可以看到只有遇到*时才会使用pre_num, 如果下一个运算符还是*, 由于本次计算也是乘法, 相当于连乘, 因此下一个运算符*对应的下一个数字的pre_num, 需要更新为当前乘法运算子表达式的结果, 即pre_num*new_num

经过上面的转换, 乘法运算就可以直接将当前数字new_num与pre_num相乘, 而无需再考虑pre_num之前的运算符了. 这个技巧在[227][中等][栈] 基本计算器 II也是有体现的.

另外需要注意以下几点:

• 由于始终是在确定运算符的后一个数字, 而在开始时, 需要确定第一个数字, 这里需要区别对待下, 在current_index为0时, 就是在寻找第一个数字. 因此只需更新当前表达式和pre_num即可, 无需枚举它之前的运算符

• 如果枚举的数字长度大于1, 且以0开头, 这种情况于单独地把这个0拿出, 然后再继续枚举的情况相同, 因此可以剪枝

• 当寻找数字的起始位置current_index超过原数字字符串长度时, 说明已经遍历完毕, 得到了一个表达式, 就可以判断结果是否与目标target相等了

class Solution:
    def addOperators(self, num: str, target: int) -> List[str]:
        n = len(num)
        res = []
        if not n:
            return res

        def dfs(current_index, current_res, path, pre_num):
            """
            Args:
              current_index: 当前数字起始索引
              current_res: 当前表达式计算结果
              path: 当前表达式
              pre_num: 前一个数字
            """
            if current_index == n:
                if current_res == target:
                    res.append(path)
                return

            for i in range(current_index, n):
                if num[current_index] == '0' and i != current_index:  # 剪枝
                    break

                new_num = num[current_index: i + 1]
                int_num = int(new_num)
                if current_index == 0:  # 确定第一个数
                    dfs(i + 1, int_num, path + new_num, int_num)
                else:
                    dfs(i + 1, current_res + int_num, path + '+' + new_num, int_num)
                    dfs(i + 1, current_res - int_num, path + '-' + new_num, -int_num)
                    dfs(i + 1, current_res - pre_num + pre_num * int_num, path + '*' + new_num, pre_num * int_num)

        dfs(0, 0, '', 0)
        return res