侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 471 篇文章
  • 累计创建 108 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

【栈, 字符串】移除无效的括号

GabrielxD
2022-05-01 / 0 评论 / 0 点赞 / 35 阅读 / 598 字 / 正在检测是否收录...
## 题目

1249. 移除无效的括号


给你一个由 '('')' 和小写字母组成的字符串 s。 你需要从字符串中删除最少数目的 '(' 或者 ')' (可以删除任意位置的括号),使得剩下的「括号字符串」有效。 请返回任意一个合法字符串。 有效「括号字符串」应当符合以下 任意一条 要求:

  • 空字符串或只包含小写字母的字符串
  • 可以被写作 ABA 连接 B)的字符串,其中 AB 都是有效「括号字符串」
  • 可以被写作 (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 = "))(("
输出:""
解释:空字符串也是有效的

提示:

  • -2^31 <= val <= 2^31 - 1
  • poptopgetMin 操作总是在 非空栈 上调用
  • push, pop, top, and getMin最多被调用 3 * 10^4

解题

方法一:栈 StringBuilder

思路

维护一个栈 stack ,一个需要被删除的字符集合 toBeRemoved,一个需要删除的遍历字符串:

  • 如果遇到 '('
    • 入栈该 '(' 括号的索引
  • 如果遇到 ')'
    • 如果此时栈为空,则说明不可能有 '(' 与其匹配,该右括号一定是一个需要被删除的无用括号,直接把索引加入 toBeRemoved 等待删除,然后进行下一次循环。
    • 否则把 stack 顶部的 '(' 的索引弹出栈,表示匹配到一对有效括号。

完成循环后新建一个与原字符串相同的可变字符序列 sb,在 sb 中删除 stack 中剩下的索引和 toBeRemoved 中记录的索引,返回 sb.toString()

代码

class Solution {
    public String minRemoveToMakeValid(String s) {
        StringBuilder sb = new StringBuilder(s);
        Stack<Integer> stack = new Stack<>();
        List<Integer> toBeRemoved = new ArrayList<>();
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (ch == ')') {
                if (stack.isEmpty()) {
                    toBeRemoved.add(i);
                    continue;
                }
                stack.pop();
            } else if (ch == '(') {
                stack.push(i);
            }
        }
        while(!stack.isEmpty()) {
            sb = sb.deleteCharAt(stack.pop());
        }
        for (int i = toBeRemoved.size() - 1; i >= 0; i--) {
            sb = sb.deleteCharAt(toBeRemoved.get(i));
        }

        return sb.toString();
    }
}
0

评论区