leetCode Question: Remove Invalid Parentheses

Remove Invalid Parentheses

Remove the minimum number of invalid parentheses in order to make the input string valid. Return all possible results.

Note: The input string may contain letters other than the parentheses ( and ).

Examples:
"()())()" -> ["()()()", "(())()"]
"(a)())()" -> ["(a)()()", "(a())()"]
")(" -> [""]

Analysis:

In this post, I will firstly present the very basic yet workable solutions using BFS, which is implemented in C++.

Then I will explain the DFS solution which is much faster but needs a little more thinking. It is implemented in python.

BFS

First of all, notice that the problem requires all possible results, thus a search algorithm (BFS, or DFS) often would be a good option.

Considering the BFS solution, in this problem we will expand a "tree" with all its child nodes from one level to the other, until we find the leaf nodes we want. So given a string s, the mimimum number of deletion is 0, which is the string itself, also it is the root node of our tree. If it is a valid string, we're done.

Then we expand the tree by delete only 1 parentheses, each child node is one string where 1 parentheses is deleted from the root. Therefore, nodes in this level of tree, represents all possible strings where only 1 parentheses is removed.

We could check each new string and see if it is a valid one. If in current level there is at lease one valid string, the search is terminated after this level is done. Since the minimum of deletion is current level depth, while the possible valid string are all in this level.

For the implementation, we should have:

• A function to check if the string is valid or not.
• A queue for the BFS, which stores the nodes in the same level.
  • Here I use a "map" which we will eliminate the duplicate strings, so that the number of "check" could be reduced.
    Please check the C++ code below for more details.

DFS

Some will notice that in the BFS solution above, the bottleneck is the number of calls for "check". Each time we have to check all the nodes in current level and then go to next level. Alternatively, we could try using DFS.

To reduce the number of "check" being called, we could store the state (true or false) of nodes in each search path. So in next search if we go to the same node, we already have the states, which we don't have to check again.

Also, we could firstly compute the number of '(' and ')' to be removed by counting the parentheses in original string. Notice that after the removal, we still have to check the result string again.

Code (C++):

class Solution {

public:

bool check(string s, int k){

int c = 0;

for (int i=0;i<s.size();i++){

if (i!=k && s[i] == '('){ c+=1; }

if (i!=k && s[i] == ')'){ c-=1; if (c<0){return false;}}

}

return c==0;

}

vector<string> removeInvalidParentheses(string s) {

vector<string> res;

unordered_map<string, bool> mp1;

unordered_map<string, bool> mp2;

if (check(s,-1)){

res.push_back(s);

return res;

}

mp1[s] = true;

while (!mp1.empty()){

bool check_flag = false;

for (auto it1 = mp1.begin();it1!=mp1.end();it1++){

string tmp = it1->first;

for (int i=0; i < tmp.size(); i++){

string tmp2 = tmp;

tmp2.erase(i,1);

if (check(tmp, i) && mp2.find(tmp2) == mp2.end()){

res.push_back(tmp2);

check_flag = true;

}

mp2[tmp2] = true;

}

}

if (check_flag){

return res;

}else{

mp1 = mp2;

mp2.clear();

}

}

return res;

}

};

Code (Python):

class Solution(object):

def check(self, s):

c = 0

for ch in s:

if ch == '(':

c += 1

if ch == ')':

c -= 1

if c < 0:

return False

return c == 0

def dfs(self, s, d_l, d_r, res, hist):

if d_l == 0 and d_r == 0 :

if not s in res and self.check(s):

res[s] = True

elif s == "":

return

else:

for i in range(len(s)):

if not s[0:i] + s[i+1:] in hist:

hist[s[0:i] + s[i+1:]] = True

if s[i] == '(' and d_l > 0:

self.dfs(s[0:i] + s[i+1:], d_l-1, d_r, res, hist)

if s[i] == ')' and d_r > 0:

self.dfs(s[0:i] + s[i+1:], d_l, d_r-1, res, hist)

def removeInvalidParentheses(self, s):

"""

:type s: str

:rtype: List[str]

"""

res = {}

hist = {}

d_r = 0 # number of '(' to be deleted

d_l = 0 # number of ')' to be deleted

for ch in s:

if ch == '(':

d_l += 1

if ch == ')':

if d_l > 0:

d_l -= 1

else:

d_r += 1

self.dfs(s, d_l, d_r, res, hist)

return res.keys()

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 \times 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 \times 3 + 4 + 5$, and $1 + 2 \times 3 + 45$, we don't have to compute the value $1+2\times3$ 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 \times 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 $\times$ and current value 3, it looks like but a wrong expression:

$previous\ value\ 3 \times current\ number\ 3 = current\ value\ 9$
Because multiplication operator has higher precedence than addition operator, in this expression, we should firstly do $\times$, 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 \times 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;

}

};