[LeetCode] Remove Invalid Parentheses 移除非法括号

删除最小数量的无效括号，使得输入的字符串有效，返回所有可能的结果。

说明: 输入可能包含了除 ( 和 ) 以外的字符。

示例 1:

输入: "()())()"

输出: ["()()()", "(())()"]

示例 2:

输入: "(a)())()"

输出: ["(a)()()", "(a())()"]

示例 3:

输入: ")("

输出: [""]

DFS解法首先统计了多余的半括号的数量，用cnt1表示多余的左括号，cnt2表示多余的右括号，因为给定字符串左右括号要么一样多，要么左括号多，要么右括号多，也可能左右括号都多，比如")("。所以cnt1和cnt2要么都为0，要么都大于0，要么一个为0，另一个大于0。好，下面进入我们的递归函数，首先判断，如果当cnt1和cnt2都为0时，说明此时左右括号个数相等了，我们调用isValid子函数来判断是否正确，正确的话加入结果res中并返回即可。否则从start开始遍历，这里的变量start表示当前递归开始的位置，我们不需要每次都从头开始，会有大量重复计算。而且对于多个相同的半括号在一起，我们只删除第一个，比如"())"，这里有两个右括号，我们不管删第一个还是删第二个右括号都会得到"()"，没有区别，所以只用算一次就行了，我们通过和上一个字符比较，如果不相同，说明是第一个右括号，如果相同则直接跳过。此时来看如果cnt1大于0，说明此时左括号多，而如果当前字符正好是左括号的时候，我们可以删掉当前左括号，继续调用递归，此时cnt1的值就应该减1，因为已经删掉了一个左括号。同理，如果cnt2大于0，说明此时右括号多，而如果当前字符正好是右括号的时候，我们可以删掉当前右括号，继续调用递归，此时cnt2的值就应该减1，因为已经删掉了一个右括号。参见代码如下：

class Solution(object):

def removeInvalidParentheses(self, s):

"""

:type s: str

:rtype: List[str]

"""

if len(s) == 0:

return [""]

count1 = 0

count2 = 0

for str_num in s:

count1 += (str_num=="(")

if count1 == 0:

count2 += (str_num==")")

else:

count1 -= (str_num==")")

start = 0

res = []

self.DFS(s, start, count1, count2, res)

return res

def DFS(self, s, start, count1, count2, res):

if count1 == 0 and count2 == 0: #一样多

if self.isValid(s):

res.append(s)

return

else:

for i in range(start, len(s)):

if i != start and s[i] == s[i-1]:

continue #重复的只计算一次

elif count1 > 0 and s[i] == "(": #左多

self.DFS(s[:i]+s[i+1:], i, count1-1, count2, res)

elif count2 > 0 and s[i] == ")": #右多

self.DFS(s[:i]+s[i+1:], i, count1, count2-1, res)

def isValid(self, string):

count = 0

for i in range(len(string)):

if string[i] == "(":

count += 1

elif string[i] == ")":

count -= 1

if count < 0:

return False

return count == 0