【深度优先搜索 DFS】Leecode-301. 删除无效的括号

【题目】

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

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

示例 1：

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

示例 2：

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

示例 3：

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

【题解】

题解1：

• 思路

     列出可能的树形图，对于给出的列表逐个遍历调用dfs

• 复杂度

         时间复杂度：O(n2)，空间复杂度：O(n)

• 代码

class Solution:
    def removeInvalidParentheses(self, s: str) -> List[str]:
        res_length = -1     # 记录删除最小数量的无效括号的长度
        st = []             # 判断括号合法性的栈，用于剪枝
        ans = set()         # 记录答案（因为会重复所以要使用set来存储）     
        path = []           # 记录回溯路径
        n = len(s)

        def dfs(i: int) -> int:
            if i == len(s):
                if st == []:
                    nonlocal res_length
                    if res_length == -1:
                        # 只有第一次执行到此时才会更新res_length的值
                        res_length = len(path)
                    if len(path) == res_length:
                        ans.add(''.join(path))
                return 
            
            # 剪枝
            if n - i + len(path) < res_length:
                return 

            # 小写字母一定选 与st无关
            if s[i] not in '()':
                path.append(s[i])
                dfs(i + 1)
                path.pop()
            else:
                # 选
                path.append(s[i])   # 记录路径
                if s[i] == '(':
                    st.append(s[i]) # '(' 入栈
                    dfs(i + 1)
                    st.pop()        # 恢复现场
                elif s[i] == ')' and st:
                    last = st.pop() # ')' 出栈
                    dfs(i + 1)
                    st.append(last) # 恢复现场
                path.pop()          # 恢复现场

                # 不选
                dfs(i + 1)
        
        dfs(0)  # 回溯入口
        return list(ans)