# 301. 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`)`.

Example 1:

``````Input:
"()())()"

Output:
["()()()", "(())()"]
``````

Example 2:

``````Input:
"(a)())()"

Output:
["(a)()()", "(a())()"]
``````

Example 3:

``````Input:")("

Output: [""]
``````

Facebook Variation: any solution that results in minimum removal of parentheses

Thoughts: 楼主用了一个3-pass的方法: 先从头到尾找close比open多的，移掉; 从尾到头找open比close多的，移掉; 然后最后一遍build

``````class Solution:
def removeInvalidParentheses(self, s):
cnt = 0
idx = []
ans = ''
# forward to remove close first
for i, c in enumerate(s):
if c == '(':
cnt += 1
if c == ')':
cnt -= 1
if cnt < 0:
idx.append(i)
cnt = 0  # reset the cnt
cnt = 0
# reverse to remove open first
for i, c in enumerate(s[::-1]):
if c == ')':
cnt += 1
if c == '(':
cnt -= 1
if cnt < 0:
idx.append(len(s) - i - 1)
cnt = 0
return ''.join([s[i] for i in range(len(s)) if i not in idx])

s1= Solution()
print(s1.removeInvalidParentheses(""))
print(s1.removeInvalidParentheses("("))
print(s1.removeInvalidParentheses(")"))
print(s1.removeInvalidParentheses("(()"))
print(s1.removeInvalidParentheses("(()))"))
``````

Thoughts:

1. Expanding the set and test whether each combination is valid, once there is answer in the set , then return (we want the minimum edition)

Code: Python

``````class Solution:
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:
res = filter(isvalid, level)
if res:
return res
level = {s[:i] + s[i+1:] for s in level for i in range(len(s))}
``````