【栈, 计数】删除最外层的括号

题目

1021. 删除最外层的括号

---

有效括号字符串为空 ""、"(" + A + ")" 或 A + B ，其中 A 和 B 都是有效的括号字符串，+ 代表字符串的连接。

• 例如，""，"()"，"(())()" 和 "(()(()))" 都是有效的括号字符串。

如果有效字符串 s 非空，且不存在将其拆分为 s = A + B 的方法，我们称其为原语（primitive），其中 A 和 B 都是非空有效括号字符串。

给出一个非空有效字符串 s，考虑将其进行原语化分解，使得：s = P_1 + P_2 + ... + P_k，其中 P_i 是有效括号字符串原语。

对 s 进行原语化分解，删除分解中每个原语字符串的最外层括号，返回 s 。

示例 1：

输入：s = "(()())(())"
输出："()()()"
解释：
输入字符串为 "(()())(())"，原语化分解得到 "(()())" + "(())"，
删除每个部分中的最外层括号后得到 "()()" + "()" = "()()()"。

示例 2：

输入：s = "(()())(())(()(()))"
输出："()()()()(())"
解释：
输入字符串为 "(()())(())(()(()))"，原语化分解得到 "(()())" + "(())" + "(()(()))"，
删除每个部分中的最外层括号后得到 "()()" + "()" + "()(())" = "()()()()(())"。

示例 3：

输入：s = "()()"
输出：""
解释：
输入字符串为 "()()"，原语化分解得到 "()" + "()"，
删除每个部分中的最外层括号后得到 "" + "" = ""。

提示：

• 1 <= s.length <= 10^5
• s[i] 为 '(' 或 ')'
• s 是一个有效括号字符串

解题

方法一：栈

思路

遍历 s，并用一个栈(stack)来表示括号的深度。遇到 '(' 则将字符入栈，遇到 ')' 则将栈顶字符出栈。栈从空到下一次空的过程，则是扫描了一个原语的过程。一个原语中，首字符和尾字符应该舍去，其他字符需放入结果字符串中。因此：

• 在遇到 '(' 并将字符入栈后，如果栈的深度为 1，则不把字符放入结果；
• 在遇到 ')' 并将栈顶字符出栈后，如果栈为空，则不把字符放入结果。
• 其他情况下，需要把字符放入结果。

代码

class Solution {
    public String removeOuterParentheses(String s) {
        Deque<Character> stack = new LinkedList<>();
        StringBuilder ans = new StringBuilder();
        for (char curr : s.toCharArray()) {
            switch (curr) {
                case '(':
                    stack.push('curr');
                    if (stack.size() > 1) ans.append(curr);
                    break;
                case ')':
                    stack.pop();
                    if (stack.size() > 0) ans.append(curr);
                    break;
            }
        }
        return ans.toString();
    }
}

简化判断

class Solution {
    public String removeOuterParentheses(String s) {
        Deque<Character> stack = new LinkedList<>();
        StringBuilder ans = new StringBuilder();
        for (char curr : s.toCharArray()) {
            if (curr == ')') stack.pop();
            if (!stack.isEmpty()) ans.append(curr);
            if (curr == '(') stack.push(curr);
        }
        return ans.toString();
    }
}

优化

由上面代码可以看出，我们只关心栈的深度，不关心栈里有什么，只需要维护栈深度(depth)即可。

class Solution {
    public String removeOuterParentheses(String s) {
        int depth = 0;
        StringBuilder ans = new StringBuilder();
        for (char curr : s.toCharArray()) {
            if (curr == ')') depth--;
            if (depth > 0) ans.append(curr);
            if (curr == '(') depth++;
        }
        return ans.toString();
    }
}

另一种理解：计数

思路

初始化计数器(count)，遍历字符串 s ：

• 遇到左括号 '(' 则将 count 加上 1
• 遇到右括号 ')' 则将 count 减去 1

找规律：

代码

class Solution {
    public String removeOuterParentheses(String s) {
        StringBuilder ans = new StringBuilder();
        int count = 0;
        for (char curr : s.toCharArray()) {
            switch (curr) {
                case '(':
                    count++;
                    if (count > 1) ans.append(curr);
                    break;
                case ')':
                    count--;
                    if (count > 0) ans.append(curr);
                    break;
            }
        }
        return ans.toString();
    }
}