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()