题目

标题和出处

标题：反转每对括号间的子串

出处：1190. 反转每对括号间的子串

难度

5 级

题目描述

要求

给出一个字符串 （仅含有小写英语字母和括号）。

请你按照从括号内到外的顺序，逐层反转每对匹配括号中的字符串，并返回最终的结果。

注意，结果中不应包含任何括号。

示例

示例 1：

输入：%22%7D#card=math&code=%5Ctexttt%7Bs%20%3D%20%22%28abcd%29%22%7D&id=kZazB)
输出：

示例 2：

输入：i)%22%7D#card=math&code=%5Ctexttt%7Bs%20%3D%20%22%28u%28love%29i%29%22%7D&id=PvVLb)
输出：
解释：先反转子字符串 ，然后反转整个字符串。

示例 3：

输入：)el)%22%7D#card=math&code=%5Ctexttt%7Bs%20%3D%20%22%28ed%28et%28oc%29%29el%29%22%7D&id=LOW8J)
输出：
解释：先反转子字符串 ，接着反转 ，然后反转整个字符串。

示例 4：

输入：p)q%22%7D#card=math&code=%5Ctexttt%7Bs%20%3D%20%22a%28bcdefghijkl%28mno%29p%29q%22%7D&id=P3Nm8)
输出：

数据范围

• 
• 中只有小写英语字母和括号
• 题目测试用例确保所有括号都是成对出现的

解法一

思路和算法

由于给定的字符串 的所有括号都是成对出现的，因此每个右括号都有一个左括号匹配。从左到右遍历字符串 ，每次遇到的右括号都是最内层的右括号。由于题目要求从最内层开始反转，因此每次遇到右括号时，就找到对应的左括号，反转这对左右括号之间的字符串，然后去掉这对左右括号，遍历结束时即可得到反转后的字符串。

对于每个右括号需要寻找匹配的左括号，可以使用栈实现。

从左到右遍历字符串 ，模拟反转操作。对于每个字符，如果该字符是字母或左括号，则将该字符入栈，如果该字符是右括号，则将栈内的字符出栈，直到遇到左括号，将左括号出栈之后，将出栈的字符按照出栈顺序依次入栈。在上述操作之后，最内层的左右括号被去掉，且左右括号之间的字符被反转。

遍历结束时，栈内元素按照从栈底到栈顶的顺序得到的字符串即为结果字符串。由于只有栈顶元素可以出栈，因此需要将栈内元素依次出栈拼接到结果字符串，然后将结果字符串反转。

下面是示例 3 的模拟过程。

字符串 ，长度为 。

下标 到 的字符都是字母和左括号，因此每个字符都入栈。此时栈为 ，其中左边为栈底，右边为栈顶。

下标 的字符是右括号，因此将 、、 出栈，然后将 和 入栈（注意入栈顺序和出栈顺序相同）。此时栈为 。

下标 的字符是右括号，因此将 、、、、 出栈，然后将 、、、 入栈。此时栈为 。

下标 到下标 的字符都是字母，因此每个字符都入栈。此时栈为 。

下标 的字符是右括号，由于与当前右括号匹配的左括号位于栈底，因此将栈内元素全部出栈，然后将除了左括号以外的出栈元素按照出栈顺序依次入栈。此时栈为 。

此时遍历结束，将栈内元素依次出栈拼接到结果字符串，得到 ，然后将结果字符串反转，得到 。

代码

class Solution {
    public String reverseParentheses(String s) {
        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.push(c);
            } else {
                StringBuffer temp = new StringBuffer();
                int count = 0;
                while (stack.peek() != '(') {
                    temp.append(stack.pop());
                    count++;
                }
                stack.pop();
                for (int j = 0; j < count; j++) {
                    stack.push(temp.charAt(j));
                }
            }
        }
        StringBuffer sb = new StringBuffer();
        while (!stack.isEmpty()) {
            sb.append(stack.pop());
        }
        sb.reverse();
        return sb.toString();
    }
}

复杂度分析

• 时间复杂度：#card=math&code=O%28n%5E2%29&id=aE1Dt)，其中 是字符串 的长度。需要遍历字符串 一次，每一层括号之间的字符串反转的时间复杂度是 #card=math&code=O%28n%29&id=Pafvb)，因此总时间复杂度是 #card=math&code=O%28n%5E2%29&id=I1yqg)。
• 空间复杂度：#card=math&code=O%28n%29&id=rGPeY)，其中 是字符串 的长度。空间复杂度主要取决于栈空间和存储出栈元素的 类型的对象，空间复杂度是 #card=math&code=O%28n%29&id=etNDH)。

解法二

思路和算法

解法一模拟反转操作，存在对同一个字符多次反转的情况，因此时间复杂度较高。可以换一个思路，不模拟反转操作，而是直接拼接结果字符串。

在没有括号的情况下，字符应按照从左到右的顺序拼接到结果字符串。如果遇到了括号，则每进入更深一层，字符串的顺序都需要反转。按照反转后的顺序遍历更深一层的字符时，需要首先找到与当前括号匹配的另一个括号，移动到另一个括号，然后从另一个括号开始按照相反顺序遍历字符。

具体而言，可能有以下几种情况：

• 从左到右遍历，遇到左括号，则移动到匹配的右括号，然后从右括号开始从右到左遍历；
• 从左到右遍历，遇到右括号，则移动到匹配的左括号，然后从左括号开始从右到左遍历；
• 从右到左遍历，遇到左括号，则移动到匹配的右括号，然后从右括号开始从左到右遍历；
• 从右到左遍历，遇到右括号，则移动到匹配的左括号，然后从左括号开始从左到右遍历。

为了知道每个括号匹配的括号，需要使用栈进行预处理括号匹配关系。遍历字符串 ，遇到左括号则将左括号所在下标入栈，遇到右括号则将栈顶元素出栈，出栈元素即为与当前右括号匹配的左括号下标。使用数组存储匹配的左右括号下标，即可在 #card=math&code=O%281%29&id=CJhTv) 的时间内得到每个括号的匹配的括号的下标。

预处理括号匹配关系之后，遍历字符串 拼接结果字符串。具体做法如下。

1. 初始化下标 ，遍历方向 表示从左到右遍历。
2. 根据字符串 在下标 处的字符，进行如下操作：
   • 如果是字母，则将该字母拼接到结果字符串；
   • 如果是括号，则将 更新为与当前括号匹配的括号下标，并将 取相反数表示将遍历方向反向。
3. 令 ，此时 移动到下一个需要遍历的字符。
4. 重复第 2 步和第 3 步，直到 超出字符串 的下标范围，此时遍历结束，返回结果字符串。

下面是示例 3 的计算过程。

字符串 ，长度为 。

预处理括号匹配的数组 （其中 表示非括号字符没有匹配的括号）。

遍历过程会依次经过如下字符：

只有字母会拼接到结果字符串中，因此结果字符串是 。

代码

class Solution {
    public String reverseParentheses(String s) {
        int length = s.length();
        int[] match = new int[length];
        Arrays.fill(match, -1);
        Deque<Integer> stack = new ArrayDeque<Integer>();
        for (int i = 0; i < length; i++) {
            char c = s.charAt(i);
            if (c == '(') {
                stack.push(i);
            } else if (c == ')') {
                int left = stack.pop();
                match[left] = i;
                match[i] = left;
            }
        }
        StringBuffer sb = new StringBuffer();
        int index = 0, direction = 1;
        while (index < length) {
            char c = s.charAt(index);
            if (Character.isLetter(c)) {
                sb.append(c);
            } else {
                index = match[index];
                direction = -direction;
            }
            index += direction;
        }
        return sb.toString();
    }
}

复杂度分析

• 时间复杂度：#card=math&code=O%28n%29&id=F5SnF)，其中 是字符串 的长度。需要遍历字符串 一次预处理括号匹配关系，拼接结果字符串需要遍历字符串 ，其中每个字母最多遍历 次，每个括号最多遍历 次，因此总时间复杂度是 #card=math&code=O%28n%29&id=NKMrH)。
• 空间复杂度：#card=math&code=O%28n%29&id=MPsBr)，其中 是字符串 的长度。空间复杂度主要取决于栈空间和存储括号匹配关系的数组，以及存储结果字符串 类型的对象，空间复杂度是 #card=math&code=O%28n%29&id=bjjUb)。