删除无效的括号

难度: Hard

给你一个由若干括号和字母组成的字符串 s ，删除最小数量的无效括号，使得输入的字符串有效。

返回所有可能的结果。答案可以按 任意顺序 返回。

示例 1：

输入：s = "()())()"
输出：["(())()","()()()"]

示例 2：

输入：s = "(a)())()"
输出：["(a())()","(a)()()"]

示例 3：

输入：s = ")("
输出：[""]

提示：

1 <= s.length <= 25
s 由小写英文字母以及括号 '(' 和 ')' 组成
s 中至多含 20 个括号

Submission

运行时间: 58 ms

内存: 16.0 MB

class Solution:
    def removeInvalidParentheses(self, s: str) -> List[str]:
        left, right = 0, 0
        for i, c in enumerate(s):
            if c == '(': 
                left +=1
            elif c == ')':
                if left == 0:
                    right +=1
                else:
                    left -=1
        ans = []
        def dfs(s:str, open:int, l:int, r:int) ->None:
            if l == 0 and r == 0:
                if self.isValid(s):
                    ans.append(s)
            
            for i in range(open, len(s)):
                if i > open and s[i] == s[i-1]:
                    continue
                if l + r > len(s) - i:
                    break
                if l >0 and s[i] == '(':
                    dfs(s[:i] + s[i+1:], i, l-1, r)
                if r > 0 and s[i] == ')':
                    dfs(s[:i] + s[i+1:], i, l, r-1)
        dfs(s,0, left, right)
        return ans
    def isValid(self, str):
        cnt = 0
        for c in str:
            if c == '(':
                cnt += 1
            elif c == ')':
                cnt -= 1
                if cnt < 0:
                    return False
        return cnt == 0

Explain

这个题解采用深度优先搜索（DFS）的方法来解决删除无效括号的问题。首先，通过遍历字符串，统计需要删除的左括号和右括号的数量。然后，使用DFS递归地尝试删除字符串中的左括号或右括号，直到删除的数量满足要求。在递归过程中，如果当前字符串已经删除了所有需要删除的括号，就判断当前字符串是否有效，如果有效则加入结果集。为了避免重复结果，在递归时跳过连续相同的字符。

时间复杂度: O(2^n)

空间复杂度: O(n)

```python
class Solution:
    def removeInvalidParentheses(self, s: str) -> List[str]:
        left, right = 0, 0
        for i, c in enumerate(s):
            if c == '(': 
                left += 1
            elif c == ')':
                if left == 0:
                    right += 1
                else:
                    left -= 1
        
        ans = []
        
        def dfs(s: str, open: int, l: int, r: int) -> None:
            if l == 0 and r == 0:
                if self.isValid(s):
                    ans.append(s)
            
            for i in range(open, len(s)):
                if i > open and s[i] == s[i-1]:
                    continue
                if l + r > len(s) - i:
                    break
                if l > 0 and s[i] == '(':
                    dfs(s[:i] + s[i+1:], i, l-1, r)
                if r > 0 and s[i] == ')':
                    dfs(s[:i] + s[i+1:], i, l, r-1)
        
        dfs(s, 0, left, right)
        return ans
    
    def isValid(self, s: str) -> bool:
        cnt = 0
        for c in s:
            if c == '(':
                cnt += 1
            elif c == ')':
                cnt -= 1
                if cnt < 0:
                    return False
        return cnt == 0
```

Explore

在DFS函数中，`open`参数表示从哪个索引开始遍历字符串以尝试删除括号。这个参数有助于确保在递归过程中不会回到已经处理过的字符位置，从而避免无谓的重复计算和可能的错误。每次递归调用时，`open`设置为当前正在处理的字符的索引，以此确保递归处理的是当前位置之后的字符串部分。

在DFS递归中，为了避免生成重复的字符串，算法检查当前字符和前一个字符是否相同，即`if i > open and s[i] == s[i-1]`。如果相同，则跳过当前的递归调用，因为在前一个字符处已经做过相同的删除操作。这样可以有效避免由于连续相同字符的多次删除而产生相同的结果字符串，从而减少重复计算和输出重复的结果。

函数`isValid`通过遍历字符串，使用一个计数器来跟踪未匹配的`(`数量。对于每个`(`，计数器增加，对于每个`)`，计数器减少。如果在任何点计数器变为负（即出现多余的`)`），则字符串无效。如果遍历结束后计数器为零，则字符串有效。如果字符串中包含字母或其他非括号字符，这种方法依然适用，因为它只计算括号的平衡性，忽略其他字符。

在DFS函数中，`l + r > len(s) - i`这个条件用来判断是否还有足够的字符可以删除。这里`l`和`r`分别是剩余需要删除的左括号和右括号的数量，而`len(s) - i`是当前索引`i`之后的字符数量。如果需要删除的括号总数超过了剩余的字符数，那么就不可能通过进一步删除括号来使字符串有效，因此这个检查可以提前终止无效的递归路径，优化算法效率。