BiruLyu
5/30/2017 - 12:42 AM

``````// https://discuss.leetcode.com/topic/88600/c-divide-and-conquer-solution-69-ms
class Solution {
int toInt(const string& num, int i, int len) {
if (len < 1 || len > 10) return -1;
if (len > 1 && num[i] == '0') return -1;
int n = 0;
for (int j=i; j < i + len; j++) {
int val = num[j] - '0';
if (n > (numeric_limits<int>::max() - val)/10) return -1;
n = (n * 10) + val;
}
return n;
}

unordered_map<int, vector<string>> multiplyHelper(const string& num, int i, int len) {
unordered_map<int, vector<string>> result;
int n = toInt(num, i, len); // single value (no multiply)
if (n >= 0) {
result[n].push_back(num.substr(i, len));
}
if (len >= 2) {
for (int j = 1; j <= 10 && j < len; j++) {
int n = toInt(num, i, j);
if (n < 0) continue;
unordered_map<int, vector<string>> right = multiplyHelper(num, i + j, len - j);
for (auto pair : right) {
if (n == 0 || pair.first <= numeric_limits<int>::max()/n) {
for (string s : pair.second) {
result[n * pair.first].push_back(num.substr(i, j) + "*" + s);
}
}
}
}
}
return result;
}

unordered_map<int, vector<string>> addOperatorsHelper(const string& num, int i, int len, const set<int>& target) {
unordered_map<int, vector<string>> result = multiplyHelper(num, i, len); // No add/subtract
if (len >= 2) {
for (int j = 1; j < len; j++) {
unordered_map<int, vector<string>> right = multiplyHelper(num, i + j, len - j);
set<int> targetLeft;
for (auto pairRight : right) {
int right = pairRight.first;
for (int targ : target) {
if (targ >= numeric_limits<int>::min() + right) {
targetLeft.insert(targ - right);
}
if (targ <= numeric_limits<int>::max() - right) {
targetLeft.insert(targ + right);
}
}
}

unordered_map<int, vector<string>> left = addOperatorsHelper(num, i, j, targetLeft);
for (auto pairLeft : left) {
for (auto pairRight : right) {
if (pairLeft.first <= numeric_limits<int>::max() - pairRight.first) {
if (target.find(pairLeft.first + pairRight.first) != target.end()) {
for (string sleft : pairLeft.second) {
for (string sright : pairRight.second) {
result[pairLeft.first + pairRight.first].push_back(sleft + "+" + sright);
}
}
}
}
if (pairLeft.first >= numeric_limits<int>::min() + pairRight.first) {
if (target.find(pairLeft.first - pairRight.first) != target.end()) {
for (string sleft : pairLeft.second) {
for (string sright : pairRight.second) {
result[pairLeft.first - pairRight.first].push_back(sleft + "-" + sright);
}
}
}
}
}
}
}
}
return result;
}

public:
vector<string> addOperators(string num, int target) {
set<int> targetSet;
targetSet.insert(target);
unordered_map<int, vector<string>> result = addOperatorsHelper(num, 0, num.length(), targetSet);
return result[target];
}
};``````
``````public class Solution {
public List<String> addOperators(String num, int target) {
List<String> res = new ArrayList<String>();
if(num == null || num.length() == 0) return res;

DFS(num, -target, 0, 0,"", res);
return res;

}

public void DFS(String num, long sum, int k, int pre, String temp, List<String> res) {
int len = num.length();
if (sum == 0 && k == len) {
return;
}
long val = 0;
for (int i = k; i < len; i ++) {
val = val * 10 + num.charAt(i) - '0';
//if(val > Integer.MAX_VALUE) {  // testcase: "21474836481" : 2147483647
//return;
//}
if(k == 0) {
DFS(num, sum + val, i + 1, (int)val, temp + String.valueOf(val), res);
} else {
DFS(num, sum + val, i + 1, (int)val, temp + "+" + String.valueOf(val), res);
DFS(num, sum - val, i + 1, (int)(-val), temp + "-" + String.valueOf(val), res);
DFS(num, sum - pre + val * pre, i + 1, (int)val * pre, temp + "*" + String.valueOf(val), res);
}
if(num.charAt(k) == '0') {
return;
}

/*
Wrong:["0+0+0","0+0-0","0+0*0","0-0+0","0-0-0","0-0*0","0*0+0","0*0-0","0*0*0","0+00",
"0-00","0*00","00+0","00-0","00*0","000"]
Correct：["0*0*0","0*0+0","0*0-0","0+0*0","0+0+0","0+0-0","0-0*0","0-0+0","0-0-0"]

我们可以看到错误的结果中有0开头的字符串出现，明显这不是数字，所以我们要去掉这些情况，过滤方法也很简单，我们只要判断长度大于1且首字符是‘0’的字符串，将其滤去即可
*/
}
}
}

/*
"123"
6
"0"
0
"123"
1
"123"
15
""
1
*/``````