题目

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

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

示例 1:
输入: "()())()"
输出: ["()()()", "(())()"]

示例 2:
输入: "(a)())()"
输出: ["(a)()()", "(a())()"]

示例 3:
输入: ")("
输出: **[""]

方案一（BFS）

  1. class Solution:
  2.     def removeInvalidParentheses(self, s: str) -> List[str]:
  3.         # 利用BFS理解起来要远远比DFS要简单的多，因为这道题说的是删除最少的括号！！
  4.         # 如果我们每次只删除一个括号，然后观察被删除一个括号后是否合法，如果已经合法了，我们就不用继续删除了。
  5.         # 因此我们并不需要将遍历进行到底，而是层层深入，一旦达到需求，就不再深入了。
  7.         def isValid(string) -> bool:
  8.             '''判断一个字符串是否合法'''
  9.             cnt = 0
  10.             for c in string:
  11.                 if c == "(":
  12.                     cnt += 1
  13.                 elif c == ")":
  14.                     cnt -= 1
  16.                 if cnt < 0:
  17.                     return False
  19.             if cnt == 0:
  20.                 return True            
  21.             return False
  23.         # BFS算法
  24.         levels = {s}
  25.         while True:
  26.             validates = list(filter(isValid, levels))
  27.             if validates:
  28.                 return validates
  29.             # 去除一个 "(" 或 ")"
  30.             next_levels = set()
  31.             for level in levels:
  32.                 for i in range(len(level)):
  33.                     if level[i] == "(" or level[i] == ")":
  34.                         next_levels.add(level[:i]+level[i+1:])
  35.             levels = next_levels

原文

https://leetcode-cn.com/explore/interview/card/2020-top-interview-questions/288/graph/1290/
https://leetcode-cn.com/problems/remove-invalid-parentheses/solution/bfsjian-dan-er-you-xiang-xi-de-pythonjiang-jie-by-/