题目

标题和出处

标题：移除无效的括号

出处：1249. 移除无效的括号

难度

5 级

题目描述

要求

给你一个由 、‘%7D#card=math&code=%5Ctexttt%7B%60%29%27%7D&id=ZlAXr) 和小写字母组成的字符串 。

你需要从字符串中删除最少数目的括号（可以删除任意位置的括号)，使得剩下的「括号字符串」有效。请返回任意一个合法字符串。

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

• 空字符串或只包含小写字母的字符串；
• 可以被写作 （ 连接 ）的字符串，其中 和 都是有效「括号字符串」；
• 可以被写作 %7D#card=math&code=%5Ctexttt%7B%28A%29%7D&id=Hits8) 的字符串，其中 是有效的「括号字符串」。

示例

示例 1：

输入：o)de)%22%7D#card=math&code=%5Ctexttt%7Bs%20%3D%20%22lee%28t%28c%29o%29de%29%22%7D&id=DiOAR)
输出：o)de%22%7D#card=math&code=%5Ctexttt%7B%22lee%28t%28c%29o%29de%22%7D&id=aHOCM)
解释：de)%22%7D#card=math&code=%5Ctexttt%7B%22lee%28t%28co%29de%29%22%7D&id=dwPpW)、ode)%22%7D#card=math&code=%5Ctexttt%7B%22lee%28t%28c%29ode%29%22%7D&id=i8Dmc) 也是可行答案。

示例 2：

输入：b(c)d%22%7D#card=math&code=%5Ctexttt%7Bs%20%3D%20%22a%29b%28c%29d%22%7D&id=huYHO)
输出：d%22%7D#card=math&code=%5Ctexttt%7B%22ab%28c%29d%22%7D&id=iTJrZ)

示例 3：

输入：)((%22%7D#card=math&code=%5Ctexttt%7Bs%20%3D%20%22%29%29%28%28%22%7D&id=Uv9k3)
输出：
解释：空字符串也是有效的。

示例 4：

输入：d)%22%7D#card=math&code=%5Ctexttt%7Bs%20%3D%20%22%28a%28b%28c%29d%29%22%7D&id=rFfTT)
输出：d)%22%7D#card=math&code=%5Ctexttt%7B%22a%28b%28c%29d%29%22%7D&id=WrLAr)

数据范围

• 
• 可能是 、‘%7D#card=math&code=%5Ctexttt%7B%60%29%27%7D&id=cv4te) 或小写英语字母

解法

思路和算法

为了删除最少的括号使得剩下的括号平衡，应该只删除无法匹配的括号。每一对匹配的括号都包含一个左括号和一个右括号，且左括号在右括号的左边。如果一个右括号左边没有左括号和该右括号匹配，或者一个左括号右边没有右括号和该左括号匹配，则这样的括号需要移除。

由于需要记录每个括号是否需要移除，因此需要创建一个数组 记录字符串 的每个下标处的字符是否需要移除，如果下标 处的括号需要移除，则将 设为 。

可以使用栈判断每个括号是否可以匹配。从左到右遍历字符串 ，遇到字母则跳过，遇到左括号则将当前下标入栈，遇到右括号则尝试用该右括号匹配栈顶下标处的左括号，可能有以下两种情况：

• 如果栈不为空，则将栈顶元素出栈，表示匹配成功；
• 如果栈为空，则当前右括号无法和左括号匹配，因此当前右括号需要移除，将数组 的当前右括号的下标处的值设为 。

遍历结束之后，如果栈不为空，则栈内的每个元素都表示未匹配的左括号的下标，这些左括号也需要移除，将数组 的这些左括号的下标处的值设为 。

在得到每个下标处的字符是否需要移除之后，即可得到移除无效括号之后的字符串。使用 类型的变量存储移除无效括号之后的字符串，再次从左到右遍历字符串 ，对于每个下标 ，当且仅当 时将 的下标 处的字符拼接到结果字符串中。

上述解法的正确性说明如下。

1. 未移除的括号中，每个左括号在入栈之后都会被一个右括号匹配，然后出栈，因此未移除的左括号都可以匹配，同理可得，每个右括号都可以匹配一个左括号，因此未移除的右括号都可以匹配。因此所有未移除的括号都可以匹配，根据上述解法得到的结果字符串中的括号一定都是有效的。
2. 由于只有在无法匹配时才将数组 中的对应值设为 ，因此移除的括号数量一定是最少的，任何移除更少括号的操作一定无法使字符串中的括号完全匹配。

代码

class Solution {
    public String minRemoveToMakeValid(String s) {
        Deque<Integer> stack = new ArrayDeque<Integer>();
        int length = s.length();
        boolean[] remove = new boolean[length];
        for (int i = 0; i < length; i++) {
            char c = s.charAt(i);
            if (c == '(') {
                stack.push(i);
            } else if (c == ')') {
                if (!stack.isEmpty()) {
                    stack.pop();
                } else {
                    remove[i] = true;
                }
            }
        }
        while (!stack.isEmpty()) {
            remove[stack.pop()] = true;
        }
        StringBuffer sb = new StringBuffer();
        for (int i = 0; i < length; i++) {
            if (!remove[i]) {
                sb.append(s.charAt(i));
            }
        }
        return sb.toString();
    }
}

复杂度分析

• 时间复杂度：#card=math&code=O%28n%29&id=kd7Fv)，其中 是字符串 的长度。需要遍历字符串 一次判断每个字符是否需要移除，然后再次遍历字符串 拼接得到移除无效括号之后的字符串，两次遍历的时间复杂度都是 #card=math&code=O%28n%29&id=mkRVK)。
• 空间复杂度：#card=math&code=O%28n%29&id=kOR0V)，其中 是字符串 的长度。空间复杂度主要取决于栈空间和记录每个字符是否需要移除的数组，以及存储结果字符串的 类型的变量。