leetCode Question: Expression Add Operators

Expression Add Operators

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", "123"]
"232", 8 -> ["23+2", "2+32"]
"105", 5 -> ["10+5","10-5"]
"00", 0 -> ["0+0", "0-0", "00"]
"3456237490", 9191 -> []

Analysis:

Usually when we met the word "all possibilities", it means we have to search all the "paths" and check each possible solution. In other words, search (remember DFS and BFS ？) is a good way to handle this kind of problem.

So in this problem, we found the problem contains two phases:

  1. Split the numbers in the string and add operators +, - or *
  2. calculate the value of the string expression, e.g., 1+2×3

The 1st phase is that we could apply the DFS (Depth First Search). In the DFS search, for every possible positions between two numbers in the string, we has four options:

  • add operator +
  • add operator −
  • add operator ∗
  • don't add operator, go to next char

In the code level, we will have a search function which is the main part of DFS, which can be birefly summarized as follows:

search(current string, pervious number, current value){
//check string length
if current string is empty:
if current value == target //check current value and target value
save result // store result
else // current string is not empty, keep search
for i = 1 to string length // we will add operator in i-th position
convert the number from string[0 to i]
//add operator and keep searching
search (string[i:end], equation + number, previous number, current val)
search (string[i:end], equation - number, pervious number, current val)
search (string[i:end], equation * number, previous number, current val)
} // when i ==string length, we don't add operater, treat the string as a single number
}
}

The 2nd phase, a traditional way to solve it is to use the stack, to calculate the infix expression (or convert infix to postfix expression then use stack to compute the value). However, as the code shown below (C++, slow version), it exceeded the time limit for long strings. Why? Because the final value of the expression, is always computed after the whole expression is formulated, but for similar expressions (child nodes with same parent) we compute the same part muliple times. E.g., 1+2×3+4+5, and 1+2×3+45, we don't have to compute the value 1+2×3 twice.

But how can we "memorize" the values computed below and keep the operator precedence at the same time? Let's take a example, say we have expression:

1+2×3=1+6=7

In our DFS procedure, firstly we have expression
1+2=3

which can be viewed as:
1+2=3

previous value+current number=current value

Then we have met operator × and current value 3, it looks like but a wrong expression:

previous value 3×current number 3=current value 9

Because multiplication operator has higher precedence than addition operator, in this expression, we should firstly do ×, then do +. So, we have:

1+2=3
3−2+2∗3=1+6=7

which can be generalized into:

( previous value −previous number )+( previous number×current number )=current value 

Once you have the idea of the above expression, the + and − operator will be much more easier to handle.

Code (C++):

class Solution {
public:
void search(string num, string equation, long last, long cur, int& target,vector<string>& res){
if (num.size() == 0){
if (target == cur){ res.push_back(equation);}
}else{
for (int i=1;i<= num.size(); i++){
string n = num.substr(0,i);
if (n.size()> 1 && n[0] == '0'){return;}
long nl = stoll (n);
if (equation.size() > 0){
search(num.substr(i), equation + "+" + n, nl, cur + nl, target, res);
search(num.substr(i), equation + "-" + n, -nl, cur - nl, target, res);
search(num.substr(i), equation + "*" + n, last * nl, (cur - last)+(last * nl), target, res);
}else{
search(num.substr(i), n, nl, nl, target, res);
}
}
}
}
vector<string> addOperators(string num, int target) {
vector<string> res;
search(num,"",0,0, target, res);
return res;
}
};

Code (Python):

class Solution(object):
def search(self, num, eq, last, cur, target, res):
if len(num) == 0:
if cur == target:
res.append(eq)
else:
for i in range(1, len(num)+1):
n = num[0:i]
if len(n) > 1 and n[0]=='0':
return
if len(eq)>0:
self.search(num[i:], eq + '+' + n, int(n), cur + int(n), target, res)
self.search(num[i:], eq + '-' + n, -int(n), cur - int(n), target, res)
self.search(num[i:], eq + '*' + n, last*int(n), (cur-last) + (last * int(n)), target, res)
else:
self.search(num[i:], n, int(n), int(n), target, res)
def addOperators(self, num, target):
"""
:type num: str
:type target: int
:rtype: List[str]
"""
res = []
self.search(num, "", 0, 0, target, res)
return res

Code (C++, slow version):

class Solution {
public:
long calc(string eq){
stack<long> nums;
stack<char> ops;
string tmp = "";
for (int i=0;i<eq.size();i++){
if (eq[i]=='+' || eq[i]=='-' || eq[i]=='*'){
nums.push(stoll(tmp));
tmp = "";
while (!ops.empty() && ops.top()=='*'){
ops.pop();
long tmp1 = nums.top();
nums.pop();
long tmp2 = nums.top();
nums.pop();
nums.push(tmp1*tmp2);
}
ops.push(eq[i]);
}else{
tmp += eq[i];
}
}
//last number
nums.push(stoll(tmp));
while (!ops.empty()){
long tmp1 = nums.top();
nums.pop();
long tmp2 = nums.top();
nums.pop();
if (ops.top() == '+'){ nums.push(tmp2 + tmp1);}
else if (ops.top()=='-'){nums.push(tmp2 - tmp1);}
else {nums.push(tmp2*tmp1);}
ops.pop();
}
return nums.top();
}
void search(string num, string equation, int& target,vector<string>& res){
if (num.size()==1){
equation = equation + num;
if (target == calc(equation)){
res.push_back(equation);
}
}else{
for (int i=1;i<num.size(); i++){
search(num.substr(i), equation + num.substr(0,i) + "+", target, res);
search(num.substr(i), equation + num.substr(0,i) + "-", target, res);
search(num.substr(i), equation + num.substr(0,i) + "*", target, res);
}
}
}
vector<string> addOperators(string num, int target) {
vector<string> res;
search(num,"", target, res);
return res;
}
};
Labels: ,

2 comments:

Subscribe to: Post Comments (Atom)