《leetcode》：Expression Add Operators

本文主要是介绍《leetcode》：Expression Add Operators，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

Given a string that contains only digits 0-9 and a target value, return all possibilities to add binary operators (not unary) +, -, or * between the digits so they evaluate to the target value.

    Examples: "123", 6 -> ["1+2+3", "1*2*3"] "232", 8 -> ["2*3+2", "2+3*2"]"105", 5 -> ["1*0+5","10-5"]"00", 0 -> ["0+0", "0-0", "0*0"]"3456237490", 9191 -> []

思路

此题比较难，不太好想，自己在看到这个题目的时候也感觉算法思想应该是这么来做，但是就是不太清晰，不知道应该怎么来写代码来实现。

参考于这里：https://discuss.leetcode.com/topic/24523/java-standard-backtrace-ac-solutoin-short-and-clear/2

实现代码如下：

    public class Solution {private String num;private int target;public List<String> addOperators(String num, int target) {List<String> res = new ArrayList<String>();int len = num.length();if(len==0){return res;}this.num = num;this.target = target;addOperatorsHelper(res,"",0,0,0);return res;}private void addOperatorsHelper(List<String> res, String path,int pos, long eval, long mult) {if(pos==this.num.length()){if(eval==this.target){res.add(path);}return;}for(int i=pos;i<this.num.length();i++){if(i!=pos&&this.num.charAt(pos)=='0'){//多位数的第一位数不能为0break;}Long cur = Long.parseLong(this.num.substring(pos, i+1));if(pos==0){addOperatorsHelper(res,path+cur,i+1,cur,cur);}else{addOperatorsHelper(res,path+"+"+cur,i+1,eval+cur,cur);addOperatorsHelper(res,path+"-"+cur,i+1,eval-cur,-cur);//注意这里是负curaddOperatorsHelper(res,path+"*"+cur,i+1,eval-mult+cur*mult,cur*mult);}}}}

这篇关于《leetcode》：Expression Add Operators的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---