spring自定义注解

1249. 移除无效的括号

难度中等68

给你一个由 '('、')' 和小写字母组成的字符串 s。

你需要从字符串中删除最少数目的 '(' 或者 ')' （可以删除任意位置的括号)，使得剩下的「括号字符串」有效。

请返回任意一个合法字符串。

有效「括号字符串」应当符合以下 任意一条 要求：

• 空字符串或只包含小写字母的字符串
• 可以被写作 AB（A 连接 B）的字符串，其中 A 和 B 都是有效「括号字符串」
• 可以被写作 (A) 的字符串，其中 A 是一个有效的「括号字符串」

示例 1：

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

示例 2：

输入：s = "a)b(c)d"
输出："ab(c)d"

示例 3：

输入：s = "))(("
输出：""
解释：空字符串也是有效的

示例 4：

输入：s = "(a(b(c)d)"
输出："a(b(c)d)"

提示：

• 1 <= s.length <= 10^5
• s[i] 可能是 '('、')' 或英文小写字母

题解

利用栈保存 括号 和remove数组保存需要删除的索引

class Solution:
    def minRemoveToMakeValid(self, s: str) -> str:
        remove = []
        stack = []
        arr = list(s)
        for i in range(len(arr)):
            if arr[i] == '(':
                stack.append(arr[i])
                remove.append(i)
            if arr[i] == ')':
                if len(stack) == 0:
                    remove.append(i)
                else:
                    stack.pop()
                    remove.pop()
        res = []
        for i in range(len(arr)):
            if i not in remove:
                res.append(s[i])
        return "".join(res)

---

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 mym_74@163.com