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: [""]
FB超级高频题，题目含义是去掉输入字符串中的最少数目的不合法括号，使其成为合法字符串。注意字符串中可能有其他字母。
去掉最少的合法字符，且返回有多种可能，很容易想到用bfs或者dfs来做。其中使用bfs来做，主要思路是将字符串依次去掉一个字符，看是否合法，如果已经合法，就在这个长度的level上操作，不在进行下一层括号去除。代码如何：
class Solution(object):
def removeInvalidParentheses(self, s):
"""
:type s: str
:rtype: List[str]
"""
if s == "":
return [""]
res = []
self.remove(s, res)
return res
def isParenthese(self, c):
if c == '(' or c == ')':
return True
else:
return False
def isValid(self, s):
cnt = 0
for c in s:
if c == ')':
cnt -= 1
if cnt < 0:
return False
elif c == '(':
cnt += 1
return cnt == 0
def remove(self, s, res):
queue = collections.deque()
queue.append(s)
used = set()
curlevel = False
while queue:
cur = queue.popleft()
if self.isValid(cur):
res.append(cur)
#important
curlevel = True
if curlevel: #important， no process next level
continue
for i in xrange(len(cur)):
if self.isParenthese(cur[i]):
sub = cur[:i] + cur[i+1:]
if sub not in used:
queue.append(sub)
used.add(sub)
return
可以看到这种写法，在bfs的每层尝试去掉一个单边括号，判断是否合法，如果合法则加入字符串到结果中。同时为了避免重复，在每一层之前已经对某字符串进行处理，后面就需要避免对该字符串进行重复处理,同时也避免了最后重复结果的出现。
这种解法的复杂度分析：最坏是需要处理该字符串的每一层，直到最后，按每层来进行下计算：
1. n*C(n, n)
2.(n-1)*C(n,n-1)
3.(n-2)C(n, n-1)C(n-1, n-2)= (n-2)*C(n, n-2)
依次类推，所以最后的复杂度为：
n*C(n, n) + (n-1)*C(n,n-1) + (n-2)*C(n, n-2)+....+1*C(n,1) = n*(C(n-1,n-1)+C(n-1, n-2)+....C(n-1,1)) = n *2^(n-1)
这题还有一种dfs的最优解法：详见:https://leetcode.com/problems/remove-invalid-parentheses/discuss/75027/Easy-Short-Concise-and-Fast-Java-DFS-3-ms-solution 复杂度需要分析。
另常考版是返回第一个valid的：详见：https://github.com/tongzhang1994/Facebook-Interview-Coding/blob/master/301.%20Remove%20Invalid%20Parentheses.java
具体思路是正方向扫一次，反方向再扫一次 python代码如下：
class Solution(object):
def removeInvalidParentheses(self, s):
"""
only need to return one situation
:type s: str
:rtype: str
"""
if s == "":
return s
s = self.removeParentheses(s, ['(', ')'])
s = self.removeParentheses(s[::-1], [')', '('])[::-1]
return s
def removeParentheses(self, s, pair):
cnt = 0
new_s = []
for c in s:
if c == pair[0]:
cnt += 1
new_s.append(c)
elif c == pair[1]:
cnt -= 1
if cnt >= 0:
new_s.append(c)
else:
cnt = 0
else:
new_s.append(c)
print cnt
return "".join(new_s)
