【回溯】leetcode301.删除无效的括号

【回溯】leetcode301.删除无效的括号

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

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

解答：

class Solution:
    def removeInvalidParentheses(self, s: str) -> List[str]:
        #使用left和right统计出多余的左右括号的数量
        n=len(s)
        left,right=0,0
        for c in s:
            if c=='(':
                left+=1
            elif c==')':
                if left==0:
                    right+=1
                else:
                    left-=1

        #判断去除掉left个左括号，right个右括号后，字符串是否有效        
        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
        
        res=[]
        #利用回溯算法尝试搜索所有可能的去除括号的方案
        def helper(s, start, lremove, rremove):
            if lremove == 0 and rremove == 0:
                if isValid(s):
                    res.append(s)
                return
            
            #从s[start:len(s)]中取出lremove个左括号和rromove个右括号
            for  i in range(start, len(s)):
                #如果遇到连续相同的括号我们只需要搜索一次即可
                if i > start and s[i] == s[i - 1]:
                    continue
                #如果剩余的字符无法满足去掉的数量要求，直接返回
                if lremove + rremove > len(s) - i:
                    break
                #尝试去掉一个左括号
                if lremove > 0 and s[i] == '(':
                    helper(s[:i] + s[i + 1:], i, lremove - 1, rremove)
                # 尝试去掉一个右括号
                if rremove > 0 and s[i] == ')':
                    helper(s[:i] + s[i + 1:], i, lremove, rremove - 1)

        helper(s, 0, left, right)
        return res