LeetCode第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 = "))(("
输出：""
解释：空字符串也是有效的
示例 4：

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

【解题思路】

首先定义如下三个变量。

StringBuilder builder：
为了操作字符方便，比如取指定位置的字符，移除指定位置的字符（换成字符数组也可以）
Stack<Integer> stack：
用于存储需要移除的括号的位置
int count：
当来了一个左括号 count + 1，右括号则是 count - 1

所以栈操作主要是看count的值：

大于0时，表示缺少count个右括号“)”来匹配，这时候如果来了右括号，（最近的左括号的位置）出栈；

等于0时，表示括号处于平衡状态，这时候来了右括号，当前右括号的位置直接入栈，对count归零操作。

最后，字符串移除所有的stack存储的对应位置的字符。

为什么count等于0时，来了右括号需要清零呢？

count并不是维护总的括号平衡情况，而是“没有多余未匹配右括号情况下”的平衡情况。有多余未匹配的括号括号，这时候后边就算有左括号过来也无法匹配。这些右括号都是需要移除的，位置入栈即可。

【实现代码】

public String minRemoveToMakeValid(String s) {
    StringBuilder builder = new StringBuilder(s);
    Stack<Integer> stack = new Stack<>();
    int count = 0;
    char ch;
    for (int i = 0; i < builder.length(); i++) {
        ch = builder.charAt(i);
        if (ch == ')') {
            count--;
            if (count < 0) {
                stack.push(i);
                count = 0;
            } else {
                stack.pop();
            }
        } else if (ch == '(') {
            count++;
            stack.push(i);
        }
    }
    while (!stack.isEmpty()) {
        builder.deleteCharAt(stack.pop());
    }
    return builder.toString();
}

题目来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimum-remove-to-make-valid-parentheses
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。