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 -> []
[Thoughts]
这道题除了DFS,我还没想出更好的办法。需要注意的是如何处理*号。每当尝试用*号的时候,要注意处理上一次计算。比如第二个例子 “232”,当处理到2+3的时候,值是5,这时候对于下一个数字2,如果用*号,就得把上一次计算回滚,(5 - 3) + 3*2。
除此之外,没有难点。
[Code]
1: vector<string> addOperators(string num, int target) {
2: vector<string> result;
3: if(num.size() == 0) return result;
4:
5: nextStep(num, 0, target, 0, "", 0, result);
6: return result;
7: }
8:
9: void nextStep(string& numStr, int cur_index, int& target, long value, string equation, long pre_num, vector<string>& result) {
10: if(value == target && cur_index == numStr.size()) {
11: result.push_back(equation);
12: return;
13: }
14:
15: for(int i = 1; i< numStr.size() - cur_index +1; i++) {
16: if(i >1 && numStr[cur_index] == '0') break;
17: string temp = numStr.substr(cur_index, i);
18: long num = stol(temp);
19:
20: if(cur_index == 0){
21: nextStep(numStr, cur_index +i, target, num, temp, num, result);
22: continue;
23: }
24:
25: nextStep(numStr, cur_index +i, target, value + num, equation + '+' + temp, num, result);
26: nextStep(numStr, cur_index +i, target, value - num, equation + '-' + temp, -num, result);
27: nextStep(numStr, cur_index +i, target, value - pre_num + pre_num * num, equation + '*' + temp, pre_num * num, result);
28: }
29: }
No comments:
Post a Comment