JZX轻语：简

LeetCode 1249 - 移除无效括号

发表于2024年07月14日

#字符串 #栈

使用栈来维护未匹配的左括号的位置信息。如果遇到了右括号，且栈为空，则说明该右括号是多余的，需要被移除；如果栈非空，则弹出栈顶元素，表示该左括号已经匹配。最后，栈中剩余的元素即为多余的左括号，需要被移除。

对于Python而言，由于字符串是不可变的，需要将字符串转换为列表进行处理，移除操作等价于将列表对应位置的元素置为""。最后，将列表使用str.join转换为字符串返回即可。

class Solution:
    def minRemoveToMakeValid(self, s: str) -> str:
        s_list = list(s)
        left_parentheses_stack = []
        for i, ch in enumerate(s_list):
            if ch == '(':
                left_parentheses_stack.append(i)
            elif ch == ')':
                if not left_parentheses_stack:
                    s_list[i] = ''
                else:
                    left_parentheses_stack.pop()
        while left_parentheses_stack:
            s_list[left_parentheses_stack.pop()] = ''
        return ''.join(s_list)

闪念标签：LC

题目链接：https://leetcode.cn/problems/minimum-remove-to-make-valid-parentheses/