1249. Minimum Remove to Make Valid Parentheses

Loading...LeetCode

题目给的s长度在10^5，时间复杂度只能是O(n*logn)以下，遍历最多一次，直接用 Q301 的 backtracking 会TLE（即便根据当前string长度进行剪枝），所有基于树搜索的方法都应该可以排除了。

换一个办法追踪括号的开闭状态，参考 Q20，用 stack 记录左括号，遇到右括号就对对碰。或者一开始就把s转为 list，这样可以一边遍历一边生成结果字符的列表，也不需要再用stack记录多余左括号的具体位置，只要记录个数，最后从尾往头删就行了。

20. Valid Parentheses

stack

class Solution:
    def minRemoveToMakeValid(self, s: str) -> str:
        stack, redundant = [], set()
        i = 0
        for i, c in enumerate(s):
            if c == '(':
                stack.append(i)
            elif c == ')':
                if stack:
                    stack.pop()
                else:
                    redundant.add(i)
        return "".join([s[i] for i in range(len(s)) if i not in stack and i not in redundant])