发表于 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 题目链接