删除最小数量的无效括号，使得输入的字符串有效，返回所有可能的结果。
说明: 输入可能包含了除 ( 和 ) 以外的字符。
示例 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阅读更多
转载于:https://www.cnblogs.com/AcceptedLin/p/9778908.html
相关资源：JAVA上百实例源码以及开源项目