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

## 题目

1249. 移除无效的括号

---

给你一个由 '('、')' 和小写字母组成的字符串 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 = "))(("
输出：""
解释：空字符串也是有效的

提示：

• -2^31 <= val <= 2^31 - 1
• pop、top 和 getMin 操作总是在 非空栈 上调用
• 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();
    }
}