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.
Example 1:
Input: num = "123", target = 6 Output: ["1+2+3", "1*2*3"]Example 2:
Input: num = "232", target = 8 Output: ["2*3+2", "2+3*2"]Example 3:
Input: num = "105", target = 5 Output: ["1*0+5","10-5"]Example 4:
Input: num = "00", target = 0 Output: ["0+0", "0-0", "0*0"]Example 5:
Input: num = "3456237490", target = 9191 Output: []
题目
给定一个数字串S和一个值target，允许你在S中间添加加减乘符号，使得表达式结果为target，求所有添法。
思路
dfs + pruning（适当剪枝）
代码
1 class Solution { 2 public List<String> addOperators(String num, int target) { 3 List<String> res = new ArrayList<>(); 4 dfs(num, 0, 0, 0, "", res, target); 5 return res; 6 } 7 8 private void dfs(String num, int index, long sum, long last, String s, List<String> res, int target) { 9 10 if(index == num.length()) { 11 if(sum == target) { 12 res.add(s); 13 } 14 } 15 16 for(int i = index + 1; i <= num.length(); i++) { 17 String temp = num.substring(index, i); 18 if(temp.length() > 1 && temp.charAt(0) == '0') { 19 continue; 20 } 21 22 long n = Long.valueOf(temp); 23 24 if(index == 0) { 25 dfs(num, i, sum + n, n, s + n, res, target); 26 continue; 27 } 28 dfs(num, i, sum + n, n, s + "+" + n, res, target); 29 dfs(num, i, sum - n, -n, s + "-" + n, res, target); 30 dfs(num, i, (sum-last) + last * n, last * n, s + "*" + n, res, target); 31 } 32 } 33 }
转载于:https://www.cnblogs.com/liuliu5151/p/10015016.html
