力扣 301. 删除无效的括号

思路1：回溯 + dfs

1. 首先判断需要最少删除的左括号和右括号
2. 进行回溯

解法1

class Solution:
    def removeInvalidParentheses(self, s: str) -> List[str]:
        # 1. 确定最小删除的左括号数量和右括号数量
        left_del, right_del = self.get_ld_rd(s)

        ret, path = set(), []

        # 2. dfs回溯
        def dfs(i, ld, rd, score):
            nonlocal ret, path
            # 回溯终止条件
            if i >= len(s):
                # 判断结果是否合法，能够加入到结果中
                if ld == 0 and rd == 0 and score == 0:
                    ret.add("".join(path))
                return
            
            # 剪枝条件,也可是说是到目前为止能够确保下一步结果一定合法的值
            if score < 0:
                return 
            
            if s[i] == "(":
                # 删除
                if ld > 0:
                    dfs(i + 1, ld - 1, rd, score)
                # 不删除
                path.append(s[i])
                dfs(i + 1, ld, rd, score + 1)
                path.pop()
            elif s[i] == ")":
                # 删除
                if rd > 0:
                    dfs(i + 1, ld, rd - 1, score)
                # 不删除
                path.append(s[i])
                dfs(i + 1, ld, rd, score - 1)
                path.pop()
            else:
                path.append(s[i])
                dfs(i + 1, ld, rd, score)
                path.pop()
        
        dfs(0, left_del, right_del, 0)
        return list(ret)
            

    def get_ld_rd(self, s: str) -> List[int]:
        ld, rd = 0, 0
        for i in s:
            if i =="(":
                ld += 1
            elif i == ")":
                if ld > 0: ld -= 1
                else: rd += 1
            else:
                continue
        return ld, rd

思路2：bfs

就粗暴解法
逐层判断合法值，保留进行下一层，直至遍历完毕。

解法2

def removeInvalidParentheses(s):
    def isValid(s):
        score = 0
        for i in s:
            if i == "(":
                score += 1
            elif i == ")":
                if score <= 0:
                    return False
                else:
                    score -= 1
        return score == 0

    cur = {s}
    while True:
        valid = list(filter(isValid, cur))
        if valid:
            return valid
        cur = {c[:i] + c[i + 1:] for c in cur for i in range(len(c)) if c[i] in "()"}