https://leetcode-cn.com/problems/remove-invalid-parentheses/
删除最小数量的无效括号，使得输入的字符串有效，返回所有可能的结果。
说明: 输入可能包含了除 ( 和 ) 以外的字符。
示例 1:
输入: "()())()"
输出: ["()()()", "(())()"]
示例 2:
输入: "(a)())()"
输出: ["(a)()()", "(a())()"]
示例 3:
输入: ")("
输出: [""]
先扫描s，确认最少需要删除多少个左括号和右括号，记为left和right
然后DFS，对每一个括号都看一下，如果将其干掉，是否可行？
DFS函数的套路是：
先是退出判断：left和right都为0，且字符串合法
然后从上一次处理的位置开始遍历
如果是括号
如果与前一个字符相同，跳过
因为这会造成重复结果，所以跳过是个优化
如果是左括号，且left>0，则干掉该括号，然后递归DFS，参数中left--
如果是右括号，且right>0，则干掉该括号，然后递归DFS，参数中right--
没有重复括号判断也可以工作，只是效率低
class Solution:
def removeInvalidParentheses(self, s: str) -> List[str]:
# - find how many left and right parentheses should remove
left, right = 0, 0
for c in s:
if c == '(':
left += 1
elif c == ')':
if left == 0:
right += 1
else:
left -= 1
else:
# - check if valid
def is_valid(s):
level = 0
for c in s:
if c == '(':
level += 1
elif c == ')':
if level == 0:
return False
else:
level -= 1
else:
return level==0
# - dfs
def dfs(s, index, left, right, res):
from index to find ( or ),
left and right means how many ( and ) to remove
# - exit check
if (left == 0) and (right == 0) and is_valid(s):
res.append(s)
return
for i in range(index, len(s)):
c = s[i]
if c in ['(', ')']:
# - if continous ( or ), only use first one
if (i > 0) and (c == s[i-1]): continue
# - try remove ( or )
if (c == ')') and (right > 0):
dfs(s[:i]+s[i+1:], i, left, right-1, res)
elif (c == '(') and (left > 0):
dfs(s[:i]+s[i+1:], i, left-1, right, res)
else:
# - start here
res = []
dfs(s, 0, left, right, res)
return list(set(res))
