题目

标题和出处

标题：删除最外层的括号

出处：1021. 删除最外层的括号

难度

3 级

题目描述

要求

有效括号字符串为空 、%22%7D#card=math&code=%5Ctexttt%7B%22%28%22%20%2B%20A%20%2B%20%22%29%22%7D&id=h3vd6) 或 ，其中 和 都是有效的括号字符串， 代表字符串的连接。

• 例如，，%22%7D#card=math&code=%5Ctexttt%7B%22%28%29%22%7D&id=IxZNz)，)()%22%7D#card=math&code=%5Ctexttt%7B%22%28%28%29%29%28%29%22%7D&id=FJfhA) 和 (()))%22%7D#card=math&code=%5Ctexttt%7B%22%28%28%29%28%28%29%29%29%22%7D&id=nSy9q) 都是有效的括号字符串。

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

给出一个非空有效字符串 ，考虑将其进行原语化分解，使得：，其中 是有效括号字符串原语。

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

示例

示例 1：

输入：())(())%22%7D#card=math&code=%5Ctexttt%7Bs%20%3D%20%22%28%28%29%28%29%29%28%28%29%29%22%7D&id=s0dM7)
输出：()()%22%7D#card=math&code=%5Ctexttt%7B%22%28%29%28%29%28%29%22%7D&id=pUTiM)
解释：输入字符串为 ())(())%22%7D#card=math&code=%5Ctexttt%7B%22%28%28%29%28%29%29%28%28%29%29%22%7D&id=pDg8J)，原语化分解得到 ())%22%20%2B%20%22(())%22%7D#card=math&code=%5Ctexttt%7B%22%28%28%29%28%29%29%22%20%2B%20%22%28%28%29%29%22%7D&id=szn42)，删除每个部分中的最外层括号后得到 ()%22%20%2B%20%22()%22%20%3D%20%22()()()%22%7D#card=math&code=%5Ctexttt%7B%22%28%29%28%29%22%20%2B%20%22%28%29%22%20%3D%20%22%28%29%28%29%28%29%22%7D&id=ZbXio)。

示例 2：

输入：())(())(()(()))%22%7D#card=math&code=%5Ctexttt%7Bs%20%3D%20%22%28%28%29%28%29%29%28%28%29%29%28%28%29%28%28%29%29%29%22%7D&id=xwhWB)
输出：()()()(())%22%7D#card=math&code=%5Ctexttt%7B%22%28%29%28%29%28%29%28%29%28%28%29%29%22%7D&id=LFMLH)
解释：输入字符串为 ())(())(()(()))%22%7D#card=math&code=%5Ctexttt%7B%22%28%28%29%28%29%29%28%28%29%29%28%28%29%28%28%29%29%29%22%7D&id=Ki5q1)，原语化分解得到 ())%22%20%2B%20%22(())%22%20%2B%20%22(()(()))%22%7D#card=math&code=%5Ctexttt%7B%22%28%28%29%28%29%29%22%20%2B%20%22%28%28%29%29%22%20%2B%20%22%28%28%29%28%28%29%29%29%22%7D&id=sly1w)，删除每个部分中的最外层括号后得到 ()%22%20%2B%20%22()%22%20%2B%20%22()(())%22%20%3D%20%22()()()()(())%22%7D#card=math&code=%5Ctexttt%7B%22%28%29%28%29%22%20%2B%20%22%28%29%22%20%2B%20%22%28%29%28%28%29%29%22%20%3D%20%22%28%29%28%29%28%29%28%29%28%28%29%29%22%7D&id=HUDHx)。

示例 3：

输入：()%22%7D#card=math&code=%5Ctexttt%7Bs%20%3D%20%22%28%29%28%29%22%7D&id=hm1DR)
输出：
解释：输入字符串为 ()%22%7D#card=math&code=%5Ctexttt%7B%22%28%29%28%29%22%7D&id=j7AYh)，原语化分解得到 %22%20%2B%20%22()%22%7D#card=math&code=%5Ctexttt%7B%22%28%29%22%20%2B%20%22%28%29%22%7D&id=trkOZ)，删除每个部分中的最外层括号后得到 。

数据范围

• 
• 为 或 ‘%7D#card=math&code=%5Ctexttt%7B%60%29%27%7D&id=Qa9Rz)
• 是一个有效括号字符串

解法一

思路和算法

根据题目描述，给定的字符串 是有效括号字符串。在有效括号字符串中，左括号和右括号的数量相同且形成配对，因此最外层的括号也是左括号和右括号配对。

可以使用栈存储左括号，根据栈是否为空判断括号是否为最外层的括号。

从左到右遍历字符串 ，遇到左括号则将左括号入栈，遇到右括号则将栈顶的左括号出栈，表示当前的右括号和栈顶的左括号配对。对于左括号，如果入栈之前栈为空，则该左括号为最外层的括号；对于右括号，如果将栈顶的左括号出栈之后栈为空，则该右括号为最外层的括号。

根据上述规则，只需要遍历字符串一次，对于每个字符可以在 #card=math&code=O%281%29&id=T95Wn) 的时间内判断该字符是否为最外层的括号。将不是最外层的括号的字符拼接到结果字符串，最终得到的结果字符串即为删除最外层的括号之后的结果。

实现方面，对于字符 ，依次执行以下操作，等价于上述规则：

1. 判断 是否是右括号，如果是右括号，则将栈顶的左括号出栈；
2. 如果栈不为空，则 不是最外层的括号，将 拼接到结果字符串；
3. 判断 是否是左括号，如果是左括号，则将 入栈。

代码

class Solution {
    public String removeOuterParentheses(String s) {
        StringBuffer sb = new StringBuffer();
        Deque<Character> stack = new ArrayDeque<Character>();
        int length = s.length();
        for (int i = 0; i < length; i++) {
            char c = s.charAt(i);
            if (c == ')') {
                stack.pop();
            }
            if (!stack.isEmpty()) {
                sb.append(c);
            }
            if (c == '(') {
                stack.push(c);
            }
        }
        return sb.toString();
    }
}

复杂度分析

• 时间复杂度：#card=math&code=O%28n%29&id=qHnIV)，其中 是字符串 的长度。需要遍历字符串 一次，每次入栈、出栈和拼接字符串的时间都是 #card=math&code=O%281%29&id=HUzqZ)。
• 空间复杂度：#card=math&code=O%28n%29&id=y4JFA)，其中 是字符串 的长度。空间复杂度主要取决于栈空间和额外创建的 或 类型的对象，空间复杂度是 #card=math&code=O%28n%29&id=DUZ7H)。

解法二

思路和算法

也可以不用栈，而是使用计数的方式删除最外层的括号。

具体做法是，使用 记录当前括号所在层数，初始时 。遍历字符串 ，遇到左括号则将 加 ，遇到右括号则将 减 。对于左括号，如果将 的值加 之前栈为空，则该左括号为最外层的括号；对于右括号，如果将 的值减 之后栈为空，则该右括号为最外层的括号。

根据上述规则，只需要遍历字符串一次，对于每个字符可以在 #card=math&code=O%281%29&id=j3tXM) 的时间内判断该字符是否为最外层的括号。将不是最外层的括号的字符拼接到结果字符串，最终得到的结果字符串即为删除最外层的括号之后的结果。

实现方面，对于字符 ，依次执行以下操作，等价于上述规则：

1. 判断 是否是右括号，如果是右括号，则将 的值减 ；
2. 如果 ，则 不是最外层的括号，将 拼接到结果字符串；
3. 判断 是否是左括号，如果是左括号，则将 的值加 。

代码

class Solution {
    public String removeOuterParentheses(String s) {
        StringBuffer sb = new StringBuffer();
        int level = 0;
        int length = s.length();
        for (int i = 0; i < length; i++) {
            char c = s.charAt(i);
            if (c == ')') {
                level--;
            }
            if (level > 0) {
                sb.append(c);
            }
            if (c == '(') {
                level++;
            }
        }
        return sb.toString();
    }
}

复杂度分析

• 时间复杂度：#card=math&code=O%28n%29&id=Bmyi6)，其中 是字符串 的长度。需要遍历字符串 一次，每次更新计数和拼接字符串的时间都是 #card=math&code=O%281%29&id=aMdu0)。
• 空间复杂度：#card=math&code=O%28n%29&id=FWH1i)，其中 是字符串 的长度。需要额外创建一个长度为 的 或 类型的对象。由于 Java 中的 类型的对象不可变，因此空间复杂度至少为 #card=math&code=O%28n%29&id=nKLMn)。