282. Expression Add Operators
Problem:
The idea is plain DFS, the difficulty lies in how to deal with multiply.
2+3*2, the prev value is 5, we cant simply multiply 5 by 2.
The correct formula is 5 - 3 + 3 * 2
val - prev + prev * cur
So we need to maintain prev value. When the previous operator is - or * =, the previous value is -cur or cur * pre respectively.
Another point worth to mention is that leading 0 is not allowed.
Solution:
Use StringBuilder is much faster than plus Strings.
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 -> []Analysis:
The idea is plain DFS, the difficulty lies in how to deal with multiply.
2+3*2, the prev value is 5, we cant simply multiply 5 by 2.
The correct formula is 5 - 3 + 3 * 2
val - prev + prev * cur
So we need to maintain prev value. When the previous operator is - or * =, the previous value is -cur or cur * pre respectively.
Another point worth to mention is that leading 0 is not allowed.
Solution:
Use StringBuilder is much faster than plus Strings.
class Solution { public List<String> addOperators(String num, int target) { List<String> res = new ArrayList<>(); if (num == null && num.length() == 0) return res; dfs(res, num, new StringBuilder(), 0, target, 0, 0); return res; } private void dfs(List<String> res, String num, StringBuilder sb, int pos, int target, long val, long pre) { if (pos == num.length() && val == target) { res.add(sb.toString()); return; } int len = sb.length(); for (int i = pos; i < num.length(); i++) { // leading 0 with 2 and more digits if (i != pos && num.charAt(pos) == '0') break; long cur = Long.parseLong(num.substring(pos, i + 1)); if (pos == 0) { dfs(res, num, sb.append(cur), i + 1, target, cur, cur); sb.setLength(len); } else { dfs(res, num, sb.append("+").append(cur), i + 1, target, val + cur, cur); sb.setLength(len); dfs(res, num, sb.append("-").append(cur), i + 1, target, val - cur, -cur); sb.setLength(len); dfs(res, num, sb.append("*").append(cur), i + 1, target, val - pre + pre * cur, cur * pre); sb.setLength(len); } } } }
评论
发表评论