301、删除无效的括号（2021-10-27）
时间：2023-02-14 21:30:00
题目
给你一个由几个括号和字母组成的字符串 s ，删除最小无效括号，使输入字符串有效。
返回所有可能的结果。答案可以根据 任意顺序 返回。
示例 1：
输入：s = "()"
输出：["()","()"]
示例 2：
输入：s = "(a)())()"
输出：["(a())()","(a)()()"]
示例 3：
输入：s = ")("
输出：[""]
提示：
1 <= s.length <= 25
s 由小写英文字母和括号组成 '(' 和 ')' 组成
s 中至多含 20 个括号
来源：力扣（LeetCode）
链接：原文链接
思路
左括号在所有合法字符串中的数量等于右括号。因此，可以得出合法字符串判断函数：
记住左括号的分数 一、右括号得分为1，合法方案最终得分为0。
以后可以用BFS每次删除一个方法 '(' 或者 )，看有没有合法的，一旦有合法的，就会返回，结果一定是括号删除最少。其中，使用set排除重复结果作为队列。
class Solution: def removeInvalidParentheses(self, s: str) -> List[str]: #判断字符串中括号是否有效 defcheck(string): #记录字符串得分，左括号 1，右括号-1 count=0; forcinstring: ifc=='(': count =1 elifc==')': count-=1 #当右括号超过左括号时，直接判断无效无需等待 ifcount<0: returnFalse #遍历后：左右相等或左>右，只有当左右括号数量相等时，有效 returncount==0 queue={s} while queue: #检查是否有合法字符串 res=list(filter(check,queue)) #有，直接返回是删除最少的 if res: return res #用set去重 temp=set() for v in queue: for i in range(len(v)): if v[i]=='(' or v[i]==')': temp.add(v[0:i] v[i 1:len(v)]) queue=temp #没有合法的字符串，返回空 return [""] 
