给表达式添加运算符（回溯算法解决）

脚本之家 2022-09-23

The following article is from 数据结构和算法 Author 博哥

关注“脚本之家”，与百万开发者在一起

出处：数据结构和算法（ID：sjjghsf）

如若转载请联系原公众号

问题描述

来源：LeetCode第282题

难度：困难

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

示例 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
输出: []

提示：

1<=num.length<=10
num仅含数字
-2^31<=target<=2^31-1

回溯算法解决

这题是让在数字之间添加“+”，“-”，“*”三种符号，变成一个算术表达式，并且让算术表达式的结果等于target。解题思路就是使用回溯算法列举所有可构成的算术表达式，然后计算他们的值。

这题我们可以把它看做是一颗n叉树，除了第一个数字以外，其他的每个数字都可以在他的前面添加“+”，“-”，“*”这三种符号，这里以示例一为例画个图来看一下。

来看个视频

我们可以看到这题和566，DFS解目标和问题有点相似，不同的是第566题只能添加“+”和“-”，而这题还可以添加“*”，这里要注意“*”的优先级要比“+”和“-”高。所以在回溯算法中我们需要使用一个变量preNum来记录前面连续相乘的积，还有一点就是这里的数字需要我们截取，截取的时候数字必须是有效的，也就是数字的最前面不能是0，比如“05”这种就是无效数字。来看下代码

public List<String> addOperators(String num, int target) {
    List<String> res = new ArrayList<>();
    dfs(res, num, target, 0, 0, 0, "");
    return res;
}

/**
 * @param res    返回的结果
 * @param num    字符串num
 * @param target 目标值target
 * @param index  访问到字符串的第几个字符
 * @param preNum 前面的连续乘积（乘法的时候会用到）
 * @param sum    表达式前面计算得到的和
 * @param path   算术表达式，可以看做n叉树的路径
 */
private void dfs(List<String> res, String num, int target, int index, long preNum, long sum, String path) {
    //字符串num中所有元素都遍历完了，要指针遍历
    if (index >= num.length()) {
        //如果表达式的值等于target，说明找到了一个合适的表达式，
        //就把他加入到集合res中
        if (sum == target) {
            res.add(path);
        }
        return;
    }

    for (int i = index; i < num.length(); i++) {
        //类似于05，07这样以0开头的数字要过滤掉
        if (i != index && num.charAt(index) == '0')
            break;
        //截取字符串，转化为数字
        long number = Long.parseLong(num.substring(index, i + 1));
        if (index == 0) {
            //因为第一个数字前面是没有符号的，所以要单独处理
            dfs(res, num, target, i + 1, number, number, "" + number);
        } else {
            //在当前数字number前面可以添加"+","-","*"三种符号。
            //数字number前添加"+"
            dfs(res, num, target, i + 1, number, sum + number, path + "+" + number);
            //数字number前添加"-"
            dfs(res, num, target, i + 1, -number, sum - number, path + "-" + number);
            //数字number前添加"*"
            dfs(res, num, target, i + 1, preNum * number,
                    sum + preNum * number - preNum, path + "*" + number);
        }
    }
}