删除无效的括号

Leetcode Link: 301. 删除无效的括号 - 力扣（LeetCode）

题目

给你一个由若干括号和字母组成的字符串 s ，删除最小数量的无效括号，使得输入的字符串有效。

返回所有可能的结果。答案可以按 任意顺序 返回。

这题看了很多题解，都看不明白，最后还是自己理解着做了爆搜来的

解法一

思路： 先聊聊我开始为什么错，和这里面的一个理解上的错误

一个合规的括号字符串，一定有 nums(左括号)==nums(右括号)。但是如果只靠这个条件来判断需要删除多少个 左括号 或者多少个 右括号，是有问题的，如下

• 假设两者数量不相等，那么如果认为需要删除的括号的数量为 abs(nums(左括号)-nums(右括号))，需要删除的括号为 数量多的那个括号。显然对于)((((()是不对的
• 假设两者数量相等，那么用这种方法判断删除的括号数量为 0，显然对于 )( 这个来说是不对的。

以上的思路用来提前预知需要删除多少个括号，是不行的。然而我思路卡在了一个奇怪的地方：假设我们提前确定删除左右括号的数量分别是 def_left 和 del_right。上述思路只会出现其中一个为 0，或者两个全为 0 的结果，但是显然，对于 )(，结果为两个都是 0，但是送进 backtracking 函数中一定没有结果，所以我竟然想如果当前 del_left, del_right 没结果，就两个都+1 再从新找…

那么本题的重点在于：提前确定到底需要删除多少个左括号和右括号

如何确定呢？ 用错位法来确定：即当一个括号出现在一个错误的位置的时候，就应该被删除。可以确定，无论如何，这都是我们需要删除的 最小数量 的括号数。但是同时也可能我们删除其他位置的括号，也能得到一个合规的结果。

错位法确定删除左右括号的数量，假设del_left, del_right 初始化为0

1. 遇到 左括号 ：del_left++，即必需要删除一个左括号
2. 遇到 右括号 ：
   • 如果此时 del_left > 0，我们可以通过用当前的右括号和之前的一个左括号配对来帮忙 删除 一个左括号和当前的这个右括号，即需要 del_left--
   • 如果此时del_left == 0，没法通过配对删除，也就是说当前的右括号没有配对的左括号，那么这个右括号必需删除del_right++

下面聊回溯函数的思路

1. 停止回溯：当遍历到的位置越界了，就要停止了，并考虑是否添加到 res 中
   • 如果 del_left 或者 del_right 还有>0，说明还没删完，肯定不能添加到 res
   • 如果 del_left 或者 del_right 都为 0，也不一定能保证合规，还是需要判断一下，因为删除对应括号的时候没考虑合规的问题
2. 遇到左右括号，当对应的删除数量 >0 时，有两种情况：删除和不删除，==0 时，只有不删除一种情况
3. 遇到其他字符，不能删除

去重！

等价于同一层去重，相邻的两个一样时，就会出现重复。 这里用 set() 去重，我总是想在回溯过程中去重，这也导致我卡了很久，最后看了代码，都是用 set() 去重。 即如果没有明确思路，直接用set()去重

题解：

class Solution:
    def removeInvalidParentheses(self, s: str) -> List[str]:
        path = []
        res = set()
 
        def backtracking(i, del_left, del_right):
            nonlocal res, path
            # 停止回溯的条件
            if i >= len (s):
	            # 判断是不是合规
                if del_left == 0 and del_right == 0 and self.get_delete_info(''.join(path))==(0,0):
                    res.add(''.join(path))
                return 
 
            if s[i] == '(':
                if del_left > 0:  # 删除
                    backtracking (i+1, del_left-1, del_right)
                # 不删除
                path.append(s[i])
                backtracking(i+1, del_left, del_right)
                path.pop()
            elif s[i] == ')':
                if del_right > 0:
                    backtracking(i+1, del_left, del_right-1)
                path.append(s[i])
                backtracking(i+1, del_left, del_right)
                path.pop()
            else:
                path.append(s[i])
                backtracking(i+1, del_left, del_right)
                path.pop()
        
        del_left, del_right = self.get_delete_info(s)
        backtracking(0, del_left, del_right)
        return list(res)
 
    def get_delete_info(self, strs):
        del_left = 0
        del_right= 0
        for c in strs:
            if c == '(':
                del_left += 1
            elif c == ')':
                if del_left != 0:
                    del_left -= 1
                else:
                    del_right += 1
            else:
                continue
        return del_left, del_right

解法二

思路：基于解法一的剪枝

我们在解法一中提到，我们在回溯的过程中并没有考虑当前的括号的合规问题，只是在最后的时候判断了一下。

那么我们可以通过在回溯的过程中添加合规判断来进行剪枝，当不合规的时候，直接return

如何做？

定义一个score，假定每次添加一个(，其分数为+1；每次添加一个)，分数-1

当score<0时，说明之前有无法匹配的右括号，此时后面再遇到左括号也不行，因此此时直接return

同样，我们最后也可以用score来判断最后的结果是不是合规。

题解：

class Solution:
    def removeInvalidParentheses(self, s: str) -> List[str]:
        path = []
        res = set()
 
        def backtracking(i, del_left, del_right, score):
            nonlocal res, path
            # 停止回溯的条件
            if i >= len (s):
	            # 判断是不是合规，这里有有变化
                if del_left == 0 and del_right == 0 and score == 0: 
                    res.add(''.join(path))
                return 
 
            # 当前合规判断！
            if score < 0:
                return 
 
            if s[i] == '(':
                if del_left > 0:  # 删除
                    backtracking (i+1, del_left-1, del_right, score)
                # 不删除
                path.append(s[i])
                backtracking(i+1, del_left, del_right, score+1)
                path.pop()
            elif s[i] == ')':
                if del_right > 0:
                    backtracking(i+1, del_left, del_right-1, score)
                path.append(s[i])
                backtracking(i+1, del_left, del_right, score-1)
                path.pop()
            else:
                path.append(s[i])
                backtracking(i+1, del_left, del_right, score)
                path.pop()
        
        del_left, del_right = self.get_delete_info(s)
        backtracking(0, del_left, del_right, 0)
        return list(res)
 
    def get_delete_info(self, strs):
        del_left = 0
        del_right= 0
        for c in strs:
            if c == '(':
                del_left += 1
            elif c == ')':
                if del_left != 0:
                    del_left -= 1
                else:
                    del_right += 1
            else:
                continue
        return del_left, del_right

解法三

思路： 直接使用回溯，不提前计算需要删除的括号数量

题解：

class Solution:
    def removeInvalidParentheses(self, s: str) -> List[str]:
        path = []
        res = []
        def process (i, score):
            # 两个base case，后一个算剪枝
            if score < 0 or score > len(s)-i: 
                return
            if i == len(s) and score == 0:
                res.append("".join(path))
                return
            
            if s[i] not in "()":
                # 必需不删
                path.append(s[i])
                process(i+1, score)
                path.pop()
            else:
                # 不删
                path.append(s[i])
                if s[i] == '(':
                    process(i+1, score+1)
                elif s[i] == ')':
                    process(i+1, score-1)
                path.pop()
                # 删除
                process(i+1, score)
            
            return 
        process (0, 0)
        # 最后再统一找最大长度的，记得去重。
        # 按照长度排序后找前几个长度最大的即可
        res = sorted(list(set(res)), key = lambda x: len(x), reverse = True)
        max_len = len(res[0])
        new_res = [res[0]]
        for i in range(1, len(res)):
            if len(res[i]) == max_len:
                new_res.append(res[i])
            else:
                break
        return new_res

启发和联系