My code:
import java.util.List;
public class Solution {
public List<String> addOperators(String num, int target) {
List<String> ret = new ArrayList<String>();
if (num == null || num.length() == 0) {
return ret;
}
helper(num, "", target, 0, (long) 0, (long) 0, ret);
return ret;
}
private void helper(String num, String path, int target, int pos, long record, long multi, List<String> ret) {
if (pos == num.length()) {
if (record == target) {
ret.add(path);
}
return;
}
for (int i = pos; i < num.length(); i++) {
if (i != pos && num.charAt(pos) == '0') {
break;
}
long curr = Long.parseLong(num.substring(pos, i + 1));
if (pos == 0) {
helper(num, path + curr, target, i + 1, curr, curr, ret);
}
else {
// add
helper(num, path + "+" + curr, target, i + 1, record + curr, curr, ret);
// minus
helper(num, path + "-" + curr, target, i + 1, record - curr, -curr, ret);
// multiply
helper(num, path + "*" + curr, target, i + 1, record - multi + multi * curr, multi * curr, ret);
}
}
}
}
reference:
https://discuss.leetcode.com/topic/24523/java-standard-backtrace-ac-solutoin-short-and-clear
这道题目并没有自己做出来。看了答案。
我当时是打算用 Divide and Conquer来做的，就像burst ballon一样。但是很来发现了一个问题我午饭解决。
符号优先级问题。
比如：
"232", 8
我从index = 0 处切开。
可以拿到我想要的。
2 + 3 * 2 = 8
在 HashMap 中， "2+32" -> 8
但是当我在 index = 1处切开，
2 + 3 * 2 = 10
其实这里我算的是：
(2 + 3) * 2
但是在这里，他的字符串统一表示是： “2+32”
所以 HashMap 被重写
"2+3*2" -> 10
然后这个结果就遗失了。
所以，Divide and Conquer 很难解决这个优先级的问题。
于是看了答案，发现 DFS做得比较好。
仍然拿上个例子，
"232", 8
首先我如此
-> 2+"32"
-> (2+3)"2"
-> (2+3)+2
-> (2+3)-2
-> (2+3)2 -> (2+3-3)+32 -> 2+3*2
可以看到，用这种方式，可以很好的区别出优先级。
他其实就是存储一个变量叫做 multi
如果这一层做加法， multi = curr
如果这一层做减法， multi = -curr
如果这一层做乘法，那么我需要考虑上一层做的是什么运算
如果是加法，
record = record+pre
现在要让 pre * curr
那么,
首先， record - pre 拿到一开始的record
然后, record + pre * curr
-> record = record - pre + pre * curr
= record - multi + multi * curr
如果是减法，
record = record - pre
那么，
首先 record + pre 拿到一开始的record
然后 record - pre * curr
这里，pre = -multi,
所以，
-> record = record + pre - pre * curr
= record + (-multi) - (-multi) * curr
= record - multi + multi * curr
再把 multi * curr 作为下一层的multi 传入。
这是最重要的一个地方，解决了优先级的问题，很巧妙。
还有个注意的就是剪枝问题。
如果 i > pos 并且 num.charAt(pos) == '0' 的话，就不用继续搜索了。
比如，
"0231", 8
一开始， pos = 0, i = 0,
会搜索 “0” +-* “231”
这已经把 "231"搜索了一遍了，
之后， pos = 0, i = 1
"02" +-* "31" 完全没必要了，但运算量会很大，所以剪枝。
还有个注意的地方就是，通过字符串扫描出来的整数，都得拿long来接受，因为说不定数字就比 Integer.MAX_VALUE 还大了。
注意了这些地方后，这道题目就可以做出来了。
Anyway, Good luck, Richardo! -- 09/17/2016
