首页 > 代码库 > 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 -> []
Credits:
Special thanks to @davidtan1890 for adding this problem and creating all test cases.
Analysis:
Use recursion+backtracking. We need deal with
1. Numbers cannot start with 0
2. When do multiply, say previous value is x = a+b*c, in current layer, we get number d and do multiplying, the value should be x-b*c+b*c*d. So we need to carry the information of the last mulitplied number into next layer, i.e., b*c*d.
1 public class Solution { 2 public List<String> addOperators(String num, int target) { 3 List<String> resList = new ArrayList<String>(); 4 StringBuilder builder = new StringBuilder(); 5 addOperRecur(resList, num, target, builder, 0, 0, 0); 6 return resList; 7 } 8 9 public void addOperRecur(List<String> resList, String num, int target, StringBuilder builder, int pos, long value,10 long lastMultipledNum) {11 if (pos >= num.length() && value =http://www.mamicode.com/= target) {12 resList.add(builder.toString());13 return;14 }15 16 int builderLen = builder.length();17 for (int i = pos; i < num.length(); i++) {18 // only allow "0", not "0XXX".19 if (i > pos && num.charAt(pos) == ‘0‘)20 return;21 long curNum = Long.parseLong(num.substring(pos, i + 1));22 if (pos == 0) {23 builder.append(curNum);24 addOperRecur(resList, num, target, builder, i + 1, curNum, curNum);25 builder.setLength(builderLen);26 } else {27 builder.append(‘+‘).append(curNum);28 addOperRecur(resList, num, target, builder, i + 1, value + curNum, curNum);29 builder.setLength(builderLen);30 31 builder.append(‘-‘).append(curNum);32 addOperRecur(resList, num, target, builder, i + 1, value - curNum, -curNum);33 builder.setLength(builderLen);34 35 builder.append(‘*‘).append(curNum);36 addOperRecur(resList, num, target, builder, i + 1, value - lastMultipledNum + lastMultipledNum * curNum,37 lastMultipledNum * curNum);38 builder.setLength(builderLen);39 }40 }41 }42 }
LeetCode-Expression Add Operators
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。