301. Remove Invalid Parentheses

Remove Invalid Parentheses - LeetCodeLeetCode

删去特定括号使s变得 valid，需要删的左括号/右括号数量是恒定的（可以遍历计算出来），只是可能有多种删除位置的选择，最终目标就是找出所有有效的删除位置选择。

每一个位置都可以选择删除或者保留，但暴力遍历的时间复杂度是O(2^n)。根据已确认字符串cur的状态，可以排除一些选择（剪枝），最坏情况仍然O(2^n)，但实际小很多。

有点参考Q20，基于左右括号计数的backtracking.

20. Valid Parentheses

class Solution(object):
    def removeInvalidParentheses(self, s: str) -> List[str]:
        res = set()
        l, redundant_l, redundant_r = 0, 0, 0
        # 计算多余（须删去）的左右括号
        for i in range(len(s)):
            if s[i] == '(': l += 1
            elif s[i] == ')':
                if l > 0: l -= 1
                else: redundant_r += 1
        redundant_l = l
        
        self.backtracking(0, 0, s, 0, '', res, redundant_l, redundant_r)
        
        return res if res else ['']
                    
    
    def backtracking(self, l, r, s, idx, cur, res, redundant_l, redundant_r):
        # 到末尾了，判断当前string是不是valid
        if idx == len(s):
            if l == r and redundant_l==redundant_r==0:
                res.add(cur)
            return
        
        if s[idx] == '(':
            # 如果还有左括号多余 -> 删去当前左括号
            if redundant_l > 0:
                self.backtracking(l, r, s, idx+1, cur, res, redundant_l-1, redundant_r)
            self.backtracking(l+1, r, s, idx+1, cur+'(', res, redundant_l, redundant_r)
            
        elif s[idx] == ')':
            # 还有右括号多余
            ## 情况1: 当前左括号大于等于右括号
            ## 情况2: 当前还没有左括号
            ## -> 删去新的右括号
            if redundant_r > 0 and (l==0 or l>=r):
                self.backtracking(l, r, s, idx+1, cur, res, redundant_l, redundant_r-1)
            # 当前左括号比右括号多 -> 保留新的右括号
            if l > r:
                self.backtracking(l, r+1, s, idx+1, cur+')', res, redundant_l, redundant_r)
        
        # 非括号字符
        else:
            self.backtracking(l, r, s, idx+1, cur+s[idx], res, redundant_l, redundant_r)