【LeetCode-282】给表达式添加运算符 [难度：困难]

本文主要是介绍【LeetCode-282】给表达式添加运算符 [难度：困难]，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

原题

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

注意，返回表达式中的操作数不应该包含前导零。

来源：力扣（LeetCode）
难度：困难
链接：https://leetcode.cn/problems/expression-add-operators/description/

解法

设字符串 num 的长度为 n，为构建表达式，我们可以往 num中间的 n−1 个空隙添加 + 号、- 号或 * 号，或者不添加符号。

我们可以用「回溯法」来模拟这个过程。从左向右构建表达式，并实时计算表达式的结果。由于乘法运算优先级高于加法和减法运算，我们还需要保存最后一个连乘串（如 2*3*4）的运算结果。

定义递归函数 backtrack(expr,i,res,mul):

expr 为当前构建出的表达式；
i 表示当前的枚举到了 num 的第 i 个数字；
res 为当前表达式的计算结果；
mul为表达式最后一个连乘串的计算结果。

因此会出现两种情况：

如果 i=n，说明表达式已经构造完成，若此时有 res=target，则找到了一个可行解，我们将 expr放入答案数组中，递归结束；
如果 i<n，需要枚举当前表达式末尾要添加的符号（+号、- 号或 * 号），以及该符号之后需要截取多少位数字。设该符号之后的数字为 val，按符号分类讨论：
（1）若添加 +号，则 res 增加 val，且 val 单独组成表达式最后一个连乘串；
（2）若添加 -号，则 res减少 val，且 −val单独组成表达式最后一个连乘串；
（3）若添加 * 号，由于乘法运算优先级高于加法和减法运算，我们需要对 res撤销之前 mul的计算结果，并添加新的连乘结果mul∗val，也就是将 res减少 mul并增加 mul∗val。

 /*回溯*/
class Solution {int n;String num;int target;List<String> ans;public List<String> addOperators(String num, int target) {// 回溯this.n = num.length(); //num的长度this.num = num;this.target = target;this.ans = new ArrayList<String>(); // 存放符合条件的表达式StringBuffer expr = new StringBuffer();//存取 当前构建出的表达式backtrack(expr,0,0,0); //递归函数return ans; }/**expr:当前构建的表达式i：num的第i个数字res：当前表达式的计算结果mul：表达式最后一个连乘串结果*/public void backtrack(StringBuffer expr, int i , long res, long mul){// 如果i=n,则表达式构建完成，此时有res=target，则该表达式符合条件，放入ans中；if(i == n){if(res == target){ans.add(expr.toString());}return;}int signIndex = expr.length();//记录表达式最后的位置，也就是要插入符号的位置if(i>0){ //表达式开头不能添加符号，expr.append(0); //占位，下面用来填充符号}long val =0;//枚举截取的数字长度（取多少位），注意数字可以是单个 0 ，但不能有前导零for(int j = i;j<n && (j == i || num.charAt(i)!='0');++j){val = val*10 +num.charAt(j)-'0';//符号之后的数字expr.append(num.charAt(j));//该数填入表达式里，此时该数前面是占位的0if(i ==0){ //表达式开头不能添加符号backtrack(expr,j+1,val,val);}else{     // 枚举符号expr.setCharAt(signIndex,'+');backtrack(expr,j+1,res+val,val);expr.setCharAt(signIndex,'-');backtrack(expr,j+1,res-val,-val);expr.setCharAt(signIndex,'*');backtrack(expr,j+1,res-mul+mul*val,mul*val);}}expr.setLength(signIndex);}
}