LC301. 删除无效的括号

DFS+剪枝

def removeInvalidParentheses(self, s):
        """ :type s: str :rtype: List[str] """
        l = r = 0
        for c in s:
            if c == '(':
                l += 1
            elif c == ')':
                if l:
                    l -= 1
                else:
                    r += 1
        ans = set()
        def dfs(idx, cl, cr, dl, dr, path):
            if idx == len(s):
                if not dl and not dr:
                    ans.add(path)
                return
            if  dl + dr > len(s) - idx:              #后面的长度不够删了
                return
            if cr > cl or dl < 0 or dr < 0:
                return
            c = s[idx]
            if c == '(':
                dfs(idx+1,cl,cr,dl-1,dr, path)
            elif c == ')':
                dfs(idx+1,cl,cr,dl,dr-1, path)
            dfs(idx+1,cl+(c=='('),cr+(c==')'),dl,dr,path+c)
        dfs(0, 0, 0, l, r, "")
        return list(ans)

DFS+去重剪枝

def removeInvalidParentheses(self, s):
        """ :type s: str :rtype: List[str] """
        l , r = 0,0
        for c in s:
            if c == '(':
                l += 1
            elif c == ')':
                if l:
                    l -= 1
                else:
                    r += 1
        def helper(s):
            sum = 0
            for i in s:
                if i == "(":
                    sum += 1
                elif i == ")":
                    sum -= 1
                    if sum < 0: 
                        return False
            return sum == 0
        res = []
        def dfs(idx, dl, dr, s):
            if dl == 0 and dr == 0:
                if helper(s):
                    res.append(s)
                return 
            for i in range(idx,len(s)):
                if i > idx and s[i] == s[i-1]:           #和组合总和一样，去除第一个后面的答案
                    continue
                if dl+dr > len(s) - i:
                    break
                if dl > 0 and s[i] == "(":
                    dfs(i, dl-1 ,dr, s[:i] + s[i + 1:])
                if dr > 0 and s[i] == ")":
                    dfs(i,dl,dr-1,s[:i] + s[i + 1:])
        dfs(0,  l, r, s)
        return res