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 -> []
A classic DFS problem.
Code (Java):
public class Solution { public List<String> addOperators(String num, int target) { List<String> result = new ArrayList<>(); if (num == null || num.length() == 0) { return result; } addOperatorHelper(num, 0, target, 0, 0, "", result); return result; } private void addOperatorHelper(String num, int start, int target, long curSum, long preNum, String curResult, List<String> result) { if (start == num.length() && curSum == target) { result.add(curResult); return; } if (start == num.length()) { return; } for (int i = start; i < num.length(); i++) { String curStr = num.substring(start, i + 1); if (curStr.length() > 1 && curStr.charAt(0) == '0') { break; } long curNum = Long.parseLong(curStr); if (curResult.isEmpty()) { addOperatorHelper(num, i + 1, target, curNum, curNum, curStr, result); } else { // Multiply addOperatorHelper(num, i + 1, target, curSum - preNum + preNum * curNum, preNum * curNum, curResult + "*" + curNum, result); // Add addOperatorHelper(num, i + 1, target, curSum + curNum, curNum, curResult + "+" + curNum, result); // Subtract addOperatorHelper(num, i + 1, target, curSum - curNum, -curNum, curResult + "-" + curNum, result); } } } }
No comments:
Post a Comment