301. Remove Invalid Parentheses

  • 34.9%

https://leetcode.com/problems/remove-invalid-parentheses/#/description

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

1
2
3
4
Examples:
"()())()" -> ["()()()", "(())()"]
"(a)())()" -> ["(a)()()", "(a())()"]
")(" -> [""]

方法一:

https://discuss.leetcode.com/topic/28831/my-c-dfs-solution-16ms

My C++ DFS Solution - 16ms

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
class Solution {
public:
vector<string> removeInvalidParentheses(string s) {
unordered_set<string> result;
int left_removed = 0;
int right_removed = 0;
for(auto c : s) {
if(c == '(') {
++left_removed;
}
if(c == ')') {
if(left_removed != 0) {
--left_removed;
}
else {
++right_removed;
}
}
}
helper(s, 0, left_removed, right_removed, 0, "", result);
return vector<string>(result.begin(), result.end());
}
private:
void helper(string s, int index, int left_removed, int right_removed, int pair, string path, unordered_set<string>& result) {
if(index == s.size()) {
if(left_removed == 0 && right_removed == 0 && pair == 0) {
result.insert(path);
}
return;
}
if(s[index] != '(' && s[index] != ')') {
helper(s, index + 1, left_removed, right_removed, pair, path + s[index], result);
}
else {
if(s[index] == '(') {
if(left_removed > 0) {
helper(s, index + 1, left_removed - 1, right_removed, pair, path, result);
}
helper(s, index + 1, left_removed, right_removed, pair + 1, path + s[index], result);
}
if(s[index] == ')') {
if(right_removed > 0) {
helper(s, index + 1, left_removed, right_removed - 1, pair, path, result);
}
if(pair > 0) {
helper(s, index + 1, left_removed, right_removed, pair - 1, path + s[index], result);
}
}
}
}
};

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

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

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
class Solution {
public:
vector<string> removeInvalidParentheses(string s) {
int remove_left=0, remove_right=0, pair=0;
/*** use the unordered_set to deal with the duplicate cases ***/
unordered_set<string> result;
/*** calculate the remained # of left and right parentheses ***/
for(int i=0; i<s.size(); i++){
if(s[i]=='(') remove_left++;
else if(s[i]==')'){
if(remove_left > 0) remove_left--;
else remove_right++;
}
}
help(0, 0, remove_left, remove_right, s, "", result);
/*** change the unordered_set to vector ***/
return vector<string>(result.begin(), result.end());
}

/***
pair : record the () pair count in the solution
index : record the cur-position int the string s
remove_left : the number of left parentheses needed to delete
remove_right : the number of right parentheses needed to delete
s : origninal input string solution : the current produced string
result : stores all the satisfied solution string
***/
void help(int pair, int index, int remove_left, int remove_right, const string& s, string solution, unordered_set<string>& result){
/*** end condition ***/
if(index==s.size()){
/*** check whether the remained string solution is right ***/
if(pair==0 && remove_left==0 && remove_right==0) result.insert(solution);
return;
}
/*** left-half-parentheses ***/
if(s[index]=='('){
/*** remove the left-half-parentheses ***/
if(remove_left > 0) help(pair, index+1, remove_left-1, remove_right, s, solution, result);
/*** keep the left-half-parentheses ***/
help(pair+1, index+1, remove_left, remove_right, s, solution+s[index], result);
}
/*** right-half-parentheses ***/
else if(s[index]==')'){
/*** remove the right-half-parentheses ***/
if(remove_right > 0) help(pair, index+1, remove_left, remove_right-1, s, solution, result);
/*** keep the right-half-parentheses ***/
if(pair > 0) help(pair-1, index+1, remove_left, remove_right, s, solution+s[index], result);
}
/*** other-characters ***/
else{
help(pair, index+1, remove_left, remove_right, s, solution+s[index], result);
}
}
};

https://discuss.leetcode.com/topic/28819/c-depth-limited-dfs-3ms-eliminate-duplicates-without-hashmap

C++ Depth limited DFS 3ms. Eliminate duplicates without hashmap.

num1 and num2 stand for the number of ‘(‘ and ‘)’ to remove respectively. Duplicates arise from consecutive ‘(‘ or ‘)’. We only get rid of the first one before going a level further.

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
class Solution {
private:
bool isValid(string s) {
int sum = 0;
for(char &c : s) {
if(c == '(') ++sum;
else if(c == ')') --sum;
if(sum < 0) return false;
}
return sum == 0;
}
public:
vector<string> removeInvalidParentheses(string s) {
int num1 = 0, num2 = 0;
for(char &c : s) {
num1 += c == '(';
if (num1 == 0) {
num2 += c == ')';
} else {
num1 -= c == ')';
}
}
vector<string> ret;
dfs(s, 0, num1, num2, ret);
return ret;
}
void dfs(string s, int beg, int num1, int num2, vector<string> &ret) {
if(num1 == 0 && num2 == 0) {
if(isValid(s))
ret.push_back(s);
} else {
for(int i = beg; i < s.size(); ++i) {
string tmp = s;
if(num2 == 0 && num1 > 0 && tmp[i] == '(') {
if(i == beg || tmp[i] != tmp[i - 1]) {
tmp.erase(i, 1);
dfs(tmp, i, num1 - 1, num2, ret);
}
}
if(num2 > 0 && tmp[i] == ')') {
if(i == beg || tmp[i] != tmp[i - 1]) {
tmp.erase(i, 1);
dfs(tmp, i, num1, num2 - 1, ret);
}
}
}
}
}
};

https://discuss.leetcode.com/topic/28833/short-python-bfs

Short Python BFS

Solution 1

Being lazy and using eval for checking:

1
2
3
4
5
6
7
8
9
10
11
12
13
def removeInvalidParentheses(self, s):
level = {s}
while True:
valid = []
for s in level:
try:
eval('0,' + filter('()'.count, s).replace(')', '),'))
valid.append(s)
except:
pass
if valid:
return valid
level = {s[:i] + s[i+1:] for s in level for i in range(len(s))}

Update: Meh, ok, checking it myself isn’t that much longer, and it’s three times as fast:

Solution 2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def removeInvalidParentheses(self, s):
def isvalid(s):
ctr = 0
for c in s:
if c == '(':
ctr += 1
elif c == ')':
ctr -= 1
if ctr < 0:
return False
return ctr == 0
level = {s}
while True:
valid = filter(isvalid, level)
if valid:
return valid
level = {s[:i] + s[i+1:] for s in level for i in range(len(s))}

Solution 3

Just a mix of the above two.

1
2
3
4
5
6
7
8
9
10
11
12
13
def removeInvalidParentheses(self, s):
def isvalid(s):
try:
eval('0,' + filter('()'.count, s).replace(')', '),'))
return True
except:
pass
level = {s}
while True:
valid = filter(isvalid, level)
if valid:
return valid
level = {s[:i] + s[i+1:] for s in level for i in range(len(s))}

Solution 4

Yet another way to do isvalid.

1
2
3
4
5
6
7
8
9
10
11
12
def removeInvalidParentheses(self, s):
def isvalid(s):
s = filter('()'.count, s)
while '()' in s:
s = s.replace('()', '')
return not s
level = {s}
while True:
valid = filter(isvalid, level)
if valid:
return valid
level = {s[:i] + s[i+1:] for s in level for i in range(len(s))}

https://discuss.leetcode.com/topic/29096/python-dp-solution

Python DP Solution

We can perceive the task as minimization the number of removed parenthesis and represent the solution as recursive with parameters si - ‘Start Index’ and oc - ‘Open Count’.

DropCount = min(DropCount[si + 1][oc], DropCount[si + 1][oc + {1 if s[si] == ‘(‘ else -1}]

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
def minDrop(s, si, oc, cache, pseq):
N = len(s)

if oc < 0:
return N - si + 1

if si == N :
if oc == 0:
pseq[si][oc] = {''}
return oc

if cache[si][oc] != -1:
return cache[si][oc]


if s[si] in '()':
dc0 = 1 + minDrop(s, si + 1, oc, cache, pseq)
pseq0 = pseq[si + 1][oc]

if s[si] == '(':
dc1 = minDrop(s, si + 1, oc + 1, cache, pseq)
pseq1 = ['(' + x for x in pseq[si + 1][oc + 1]]
else:
dc1 = minDrop(s, si + 1, oc - 1, cache, pseq)
pseq1 = [')' + x for x in pseq[si + 1][oc - 1]]

cache[si][oc] = min(dc0, dc1)

# note '=' - in case of eqaulity we keep both combination sets
if dc0 >= dc1 :
pseq[si][oc] = pseq[si][oc].union(pseq1)

if dc0 <= dc1 :
pseq[si][oc] = pseq[si][oc].union(pseq0)

else:
cache[si][oc] = minDrop(s, si + 1, oc, cache, pseq)
pseq[si][oc] = [s[si] + x for x in pseq[si + 1][oc]]

return cache[si][oc]

class Solution(object):
def removeInvalidParentheses(self, s):
"""
:type s: str
:rtype: List[str]
"""
N = len(s)
cache = [[-1 for x in range(N)] for x in range(N)]
pseq = [[set() for x in range(N + 1)] for x in range(N + 1)]

c = minDrop(s, 0, 0, cache, pseq)

return list(pseq[0][0])

101ms, 40.15%, October 15, 2016

https://discuss.leetcode.com/topic/28827/share-my-java-bfs-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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
public class Solution {
public List<String> removeInvalidParentheses(String s) {
List<String> res = new ArrayList<>();

if(s == null) return res;

Set<String> visited = new HashSet<>();
Queue<String> queue = new LinkedList<>();

queue.add(s);
visited.add(s);

boolean found = false;

while(!queue.isEmpty()){
s = queue.poll();

if(isValid(s)){
res.add(s);
found = true;
}

if(found) continue;

for(int i = 0; i<s.length(); i++){
if(s.charAt(i) != '(' && s.charAt(i) != ')') continue;
String t = s.substring(0, i) + s.substring(i+1);
if(!visited.contains(t)){
queue.add(t);
visited.add(t);
}
}
}
return res;
}

boolean isValid(String s){
int count = 0;
for(int i=0; i<s.length(); i++){
char c = s.charAt(i);
if(c=='(') count++;
if(c==')' && count -- == 0) return false;
}
return count == 0;
}
}

3ms, 81.22%, October 15, 2016

https://discuss.leetcode.com/topic/34875/easy-short-concise-and-fast-java-dfs-3-ms-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
public class Solution {
public List<String> removeInvalidParentheses(String s) {
List<String> ans = new ArrayList<>();
remove(s, ans, 0, 0, new char[]{'(', ')'});
return ans;
}

public void remove(String s, List<String> ans, int last_i, int last_j, char[] par){
for(int stack = 0, i = last_i; i<s.length(); ++i){
if(s.charAt(i) == par[0]) stack++;
if(s.charAt(i) == par[1]) stack--;
if(stack >= 0) continue;
for(int j=last_j; j<=i; ++j)
if(s.charAt(j) == par[1] && (j==last_j || s.charAt(j-1) != par[1]))
remove(s.substring(0, j) + s.substring(j+1, s.length()), ans, i, j, par);
return;
}
String reversed = new StringBuilder(s).reverse().toString();
if(par[0] == '(')
remove(reversed, ans, 0, 0, new char[]{')', '('});
else
ans.add(reversed);
}
}
谢谢你,可爱的朋友。