leetcode [301] 删除无效的括号

---

Contact me:

Blog -> https://cugtyt.github.io/blog/index
Email -> cugtyt@qq.com
GitHub -> Cugtyt@GitHub

---

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

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

示例 1:

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

示例 2:

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

示例 3:

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

思路来自题解:

每次对字符串删除一个括号，生成不同的候选，如果有合法的，那么就是答案，否则，继续对候选删除括号。

class Solution:
    def removeInvalidParentheses(self, s: str) -> List[str]:
        level = {s}
        while True:  # BFS
            valid = [lev for lev in level if self.check(lev)]
            if valid:
                return valid
            level = {s[:i] + s[i + 1:] for s in level for i in range(len(s)) if s[i] in '()'}

    def check(self, s):
        count = 0
        for c in s:
            if c == '(':
                count += 1
            if c == ')':
                count -= 1
                if count < 0:
                    return False
        return count == 0