[数据结构与算法]0回溯/字符串困难 LeetCode282. 给表达式添加运算符 NC217 给表达式添加运算符

282. 给表达式添加运算符

描述

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

分析

注意：

1. 每次递归创建新的StringBuffer对象，防止本层操作影响上一层的StringBuffer。
2. 为避免越界，计算结果及当前值使用long，不使用int

每次操作分为四种：不加操作、加、减、乘。
使用回溯的思想穷尽所有的可能操作，等于target的字符串加入最终结果集合。
难点在于乘法计算，乘法优先级高于加法、减法，为了辅助实现全部可能的乘法操作，设有形参变量prepareMultiply,prepareMultiply表示待与当前数做乘法运算的数。
使用递归
参考官方题解：
https://leetcode-cn.com/problems/expression-add-operators/solution/gei-biao-da-shi-tian-jia-yun-suan-fu-by-2o1s7/
以及评论区大佬的注释
//一个比较直观的想法就是直接构造出所有的可能性，然后按照基本计算器
//的思路计算最后的结果，我试了一下也能在600+msAC，但是代码比较多
//其实一个比较难的点就在于乘号改变了运算的顺序，一开始我也觉得不好处理
//举构造乘法时的三个例子。我们用sum记录已经求得的总和，同时记录上一个处理的数lastnum
//假设已经构造了2+3，sum=5，lastnum=3，该处理4，这时该添加乘号了，对于已经求得
//的sum，这时应该减去 3，用这个3去乘4，sum=sum-3+34=14，lastnum=12；
//
//假设已经构造了2-3，sum=-1，lastnum=-3，该处理4，这时该添加乘号了，对于已经求得
//的sum，这时应该减去-3，用这个-3去乘4，sum=sum-(-3)+(-3)4=-10，lastnum=-12；
//
//假设已经构造了23，sum=6，lastnum=6，该处理4，这时该添加乘号了，对于已经求得
//的sum，这时应该减去 6，用这个6去乘4，sum=sum-6+64=24，lastnum=24；
//
//减法和乘法为什么这样操作在纸上算一下就清楚了，然后就是传递字符串的问题了，如果每次都拷贝传递
//dfs(num, path + “+” + s, sum + tmp, tmp, i + 1, target);
//dfs(num, path + “-” + s, sum - tmp, -tmp, i + 1, target);
//dfs(num, path + “*” + s, sum - lastnum + lastnum * tmp, lastnum * tmp, i + 1, target);
//虽然代码好看又简单，但是速度不够快，用一个string path来储存状态
//来加速这个过程,速度提升不少，也是回溯常用的操作

class Solution {
    int n;
    String num;
    List<String> ans;
    int target;

    public List<String> addOperators(String num, int target) {
        this.n = num.length();
        this.num = num;
        this.target = target;
        this.ans = new ArrayList<String>();
        StringBuffer expr = new StringBuffer();
        dfs(expr,0,0,0);
        return ans;
    }

    public void dfs(StringBuffer sba, long sum, long prepareMultiply, int index){
        StringBuffer sb = new StringBuffer(sba);
        if(index == n){
            if(sum == target){
                ans.add(sb.toString());
            }
            return ;
        }
        int sign = sb.length();
        if(index > 0){
            sb.append("0");
        }
        long val = 0;
        for(int i = index; i < n && (i == index || num.charAt(index) != '0'); i++){
            val = val * 10 + (num.charAt(i) - '0');
            sb.append(num.charAt(i));
            if(index == 0){
                dfs(sb,val,val,i+1);
                continue;
            }
            sb.setCharAt(sign,'+');
            dfs(sb,sum + val, val,i+1);
            sb.setCharAt(sign,'-');
            dfs(sb,sum - val, -val,i+1);
            sb.setCharAt(sign,'*');
            dfs(sb,sum - prepareMultiply + prepareMultiply * val, prepareMultiply * val,i+1);
        }
    }
}