1249-移除无效的括号

1249-移除无效的括号

输入：s = "lee(t(c)o)de)"
输出："lee(t(c)o)de"
解释："lee(t(co)de)" , "lee(t(c)ode)" 也是一个可行答案。

class Solution:
    def minRemoveToMakeValid(self, s: str) -> str:
        index_to_remove = set()
        stack = []
        # 通过遍历寻找需要删除的元素位置
        for i, c in enumerate(s):
            # 跳过字母字符
            if c not in '()':
                continue
            # 左括号入栈
            if c == '(':
                stack.append(i)
            # 栈不为空时，保存需要删除的索引位置
            elif not stack:
                index_to_remove.add(i)
            # 右括号匹配时出栈
            elif c == ')':
                stack.pop()
        # 集合合并
        index_to_remove = index_to_remove.union(set(stack))
        string_builder = []
        # 重建字符串
        for i, c in enumerate(s):
            if i not in index_to_remove:
                string_builder.append(c)
        return ''.join(string_builder)