301. 删除无效的括号

Difficulty
Hard
Tags
BFS
URL
https://leetcode-cn.com/problems/remove-invalid-parentheses/
Star
给你一个由若干括号和字母组成的字符串 s ，删除最小数量的无效括号，使得输入的字符串有效。
返回所有可能的结果。答案可以按 任意顺序 返回。
示例 1：
输入：s = "()())()"
输出：["(())()","()()()"]
示例 2：
输入：s = "(a)())()"
输出：["(a())()","(a)()()"]
示例 3：
输入：s = ")("
输出：[""]
提示：
  • 1 <= s.length <= 25
  • s 由小写英文字母以及括号 '(' 和 ')' 组成
  • s 中至多含 20 个括号
通过次数63,211提交次数115,041

法 1 BFS

思路
按照bfs的思路，第一层删掉一个字符，第二层删掉两个字符，这样一直删除下去，知道有一层中又满足的字符串，那么就停止扩散。
题解
class Solution:
    def removeInvalidParentheses(self, s: str) -> List[str]:
        queue = deque()
        queue.append(s)

        visited = set()
        visited.add(s)

        while queue:
            vaild_s = [s for s in queue if self.is_valid(s)]
            if len(vaild_s) > 0:
                return list(set(vaild_s))

            size = len(queue)
            while size:
                cur_s = queue.popleft()
                size -= 1

                for i in range(0, len(cur_s)):
                    if cur_s[i] not in {"(", ")"}:
                        continue
                    nxt_s = cur_s[0:i] + cur_s[i+1:]
                    if nxt_s in visited:
                        continue
                    visited.add(nxt_s)
                    queue.append(nxt_s)

        return [""]
        
    def is_valid(self, s):
        cnt = 0
        for char in s:
            if char == "(":
                cnt += 1
            elif char == ")":
                cnt -= 1

            if cnt < 0:
                return False

        return cnt == 0