301. 删除无效的括号

题目链接：https://leetcode.cn/problems/remove-invalid-parentheses/
难度：困难

描述：
给你一个由若干括号和字母组成的字符串 s ，删除最小数量的无效括号，使得输入的字符串有效。
返回所有可能的结果。答案可以按 任意顺序 返回。

题解

class Solution:
    def removeInvalidParentheses(self, s: str) -> List[str]:
        ret = []
        l, r = 0, 0
        for c in s:
            if c == '(':
                l += 1
            elif c == ')':
                if l == 0:
                    r += 1
                else:
                    l -= 1
        def isValid(str):
            cnt = 0
            for c in str:
                if c == '(':
                    cnt += 1
                elif c == ')':
                    cnt -= 1
                    if cnt < 0:
                        return False
            return cnt == 0
        def helper(s, start, l, r):
            if l == 0 and r == 0:
                if isValid(s):
                    ret.append(s)
                return
            for  i in range(start, len(s)):
                if i > start and s[i] == s[i - 1]:
                    continue
                if l + r > len(s) - i:
                    break
                if l > 0 and s[i] == '(':
                    helper(s[:i] + s[i + 1:], i, l - 1, r);
                if r > 0 and s[i] == ')':
                    helper(s[:i] + s[i + 1:], i, l, r - 1);
        helper(s, 0, l, r)
        return ret