282. Expression Add Operators

  • 29.1%

https://leetcode.com/problems/expression-add-operators/#/description

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.

1
2
3
4
5
6
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 -> []

https://discuss.leetcode.com/topic/24478/17-lines-solution-dfs-c

17 lines solution, dfs (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
private:
// cur: {string} expression generated so far.
// pos: {int} current visiting position of num.
// cv: {long} cumulative value so far.
// pv: {long} previous operand value.
// op: {char} previous operator used.
void dfs(std::vector<string>& res, const string& num, const int target, string cur, int pos, const long cv, const long pv, const char op) {
if (pos == num.size() && cv == target) {
res.push_back(cur);
} else {
for (int i=pos+1; i<=num.size(); i++) {
string t = num.substr(pos, i-pos);
long now = stol(t);
if (to_string(now).size() != t.size()) continue;
dfs(res, num, target, cur+'+'+t, i, cv+now, now, '+');
dfs(res, num, target, cur+'-'+t, i, cv-now, now, '-');
dfs(res, num, target, cur+'*'+t, i, (op == '-') ? cv+pv - pv*now : ((op == '+') ? cv-pv + pv*now : pv*now), pv*now, op);
}
}
}

public:
vector<string> addOperators(string num, int target) {
vector<string> res;
if (num.empty()) return res;
for (int i=1; i<=num.size(); i++) {
string s = num.substr(0, i);
long cur = stol(s);
if (to_string(cur).size() != s.size()) continue;
dfs(res, num, target, s, i, cur, cur, '#'); // no operator defined.
}

return res;
}
};

https://discuss.leetcode.com/topic/24487/accepted-c-solution

Accepted C++ Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
void addOperators(vector<string>& result, string nums, string t, long long last, long long curVal, int target) {
if (nums.length() == 0) {
if (curVal == target)
result.push_back(t);
return;
}

for (int i = 1; i<=nums.length(); i++) {
string num = nums.substr(0, i);
if(num.length() > 1 && num[0] == '0')
return;

string nextNum = nums.substr(i);

if (t.length() > 0) {
addOperators(result, nextNum, t + "+" + num, stoll(num), curVal + stoll(num), target);
addOperators(result, nextNum, t + "-" + num, -stoll(num), curVal - stoll(num), target);
addOperators(result, nextNum, t + "*" + num, last * stoll(num), (curVal - last) + (last * stoll(num)), target);
}
else
addOperators(result, nextNum, num, stoll(num), stoll(num), target);
}
}

vector<string> addOperators(string num, int target) {
vector<string> result;
addOperators(result, num, "", 0, 0, target);
return result;
}

https://discuss.leetcode.com/topic/35751/recommend-for-beginners-clean-c-implementation-with-detailed-explanation

[recommend for beginners]clean C++ implementation with detailed explanation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
vector<string> addOperators(string num, int target) {
vector<string> result;
if(num.size()==0) return result;
help(result, "", num, target, 0, 0, 0);
return result;
}

void help(vector<string> &result, string path, string num, int target, int pos, long cur, long prev){
if(pos==num.size()){
if(cur==target) result.push_back(path);
return;
}
for(int i=pos; i<num.size(); i++){
/*** corner-case-added-code ***/
if(num[pos]=='0' && i>pos) break;
string _str=num.substr(pos, i-pos+1);
long _value=stol(_str);
if(pos==0) {
help(result, path+_str, num, target, i+1, _value, _value);
}
else{
help(result, path+"+"+_str, num, target, i+1, cur+_value, _value);
help(result, path+"-"+_str, num, target, i+1, cur-_value, -_value);
help(result, path+"*"+_str, num, target, i+1, cur-prev+prev*_value, prev*_value);
}
}
}
};

https://discuss.leetcode.com/topic/24688/16ms-c-solution

16ms C++ solution

The idea is to cut a value from the left of the string and then for each of operations ‘+’, ‘-‘, ‘*‘ repeat the procedure recursively. The trick is to pass the sum of all left summands and the product of rightmost factors. This allows to calculate the left sum and the right product on the next step depending on the next chosen operation.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
class Solution {
typedef long long int i64;

string myS;
const char* s;
i64 target;
int slen;

public:

vector<string> addOperators(const string& num, int t) {
myS = num;
slen = myS.size();
s = myS.c_str();
target = t;

vector<string> res;
char buf[slen*2+1];

int lmax = (s[0] == '0' ? 1 : slen);
i64 v = 0;
for (int l=1; l<=lmax; ++l) {
int c = s[l-1];
v = v*10 + (c-'0'); // add next digit
buf[l-1] = c; // only need to append the last digit
processTail(0, v, l, buf, l, res);
}
return res;
}

void processTail(i64 prevsum, i64 last, int pos, char* buf, int bufpos, vector<string>& res) {
if (pos == slen) {
// end of string
// check the value and save
if (prevsum+last == target) {
buf[bufpos] = 0;
res.push_back(buf);
}
return;
}

int lmax = (s[pos] == '0' ? 1 : slen-pos); // don't allow multichar intergers starting from a '0'
i64 v = 0;
for (int l=1; l<=lmax; ++l) {
int c = s[pos+l-1];
v = v*10 + (c-'0'); // add next digit to v

buf[bufpos] = '+';
buf[bufpos+l] = c; // only need to append the last digit of v
processTail(prevsum+last, v, pos+l, buf, bufpos+l+1, res);

buf[bufpos] = '-';
processTail(prevsum+last, -v, pos+l, buf, bufpos+l+1, res);

buf[bufpos] = '*';
processTail(prevsum, last*v, pos+l, buf, bufpos+l+1, res);
}
}
};

2509ms, 25,85%, October 18, 2016

https://discuss.leetcode.com/topic/30089/clean-python-dfs-with-comments

Clean Python DFS with comments

dfs() parameters:

num: remaining num string

temp: temporally string with operators added

cur: current result of “temp” string

last: last multiply-level number in “temp”. if next operator is “multiply”, “cur” and “last” will be updated

res: result to return

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def addOperators(self, num, target):
res, self.target = [], target
for i in range(1,len(num)+1):
if i == 1 or (i > 1 and num[0] != "0"): # prevent "00*" as a number
self.dfs(num[i:], num[:i], int(num[:i]), int(num[:i]), res) # this step put first number in the string
return res

def dfs(self, num, temp, cur, last, res):
if not num:
if cur == self.target:
res.append(temp)
return
for i in range(1, len(num)+1):
val = num[:i]
if i == 1 or (i > 1 and num[0] != "0"): # prevent "00*" as a number
self.dfs(num[i:], temp + "+" + val, cur+int(val), int(val), res)
self.dfs(num[i:], temp + "-" + val, cur-int(val), -int(val), res)
self.dfs(num[i:], temp + "*" + val, cur-last+last*int(val), last*int(val), res)

282ms, 23.05%, October 18, 2016

https://discuss.leetcode.com/topic/24523/java-standard-backtrace-ac-solutoin-short-and-clear

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public class Solution {
public List<String> addOperators(String num, int target) {
List<String> rst = new ArrayList<String>();
if(num==null || num.length() == 0) return rst;
helper(rst, "", num, target, 0, 0, 0);
return rst;
}

public void helper(List<String> rst, String path, String num, int target, int pos, long eval, long multed){
if(pos == num.length()){
if(target == eval)
rst.add(path);
return;
}

for(int i=pos; i<num.length(); i++){
if(i != pos && num.charAt(pos) == '0') break;
long cur = Long.parseLong(num.substring(pos, i+1));
if(pos == 0)
helper(rst, path+cur, num, target, i+1, cur, cur);
else{
helper(rst, path + "+" + cur, num, target, i+1, eval+cur, cur);
helper(rst, path + "-" + cur, num, target, i+1, eval-cur, -cur);
helper(rst, path + "*" + cur, num, target, i+1, eval-multed+multed*cur, multed*cur);
}
}
}
}
谢谢你,可爱的朋友。