题目

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

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

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

方法一：栈

思路

对于括号序列相关的题，通用的解法是用递归或者栈。

从左至右地遍历整个字符串，用字符串 str 来记录当前层所遍历到的小写英文字母。对于当前遍历的字母：

如果是左括号：把 str 插入到栈中，并且把 str 置空，进入到下一层
如果是右括号：遍历到了右括号，说明当前层的字母已经遍历完了，把 str 反转，并把栈顶的字符串弹出，将反转后的 str 插入到弹出字符串的末尾，将结果赋值给 str
如果是小写英文字母：追加到 str 末尾

可以看到，只有在遍历到了右括号（第一个出现的右括号是最里面的）才会对字符串进行操作，这样可以保证能从括号里到外处理字符串

代码实现

import java.util.*;

public class test{
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.reverseParentheses("(u(love)i)"));
    }
}

//用栈实现反转每对括号间的子串
class Solution{
    public String reverseParentheses(String s){
        Deque<String> stack = new LinkedList<String>();
        StringBuffer sb = new StringBuffer();   //对字符串进行修改时，用StringBuffer类
        //对字符串s进行遍历
        for (int i = 0;i < s.length();i++){
            char ch = s.charAt(i);
            if (ch == '('){
                stack.push(sb.toString());      //toString()返回序列中的字符串
                sb.setLength(0);                //将字符串置空
            }else if (ch == ')'){
                sb.reverse();                   //字符串反转
                sb.insert(0, stack.pop());
            }else {
                sb.append(ch);                  //追加字符串到此字符串中
            }
        }
        return sb.toString();
    }
}

输出结果：

iloveu

算法主体

//用栈实现反转每对括号间的子串
class Solution{
    public String reverseParentheses(String s){
        Deque<String> stack = new LinkedList<String>();
        StringBuffer sb = new StringBuffer();   //对字符串进行修改时，用StringBuffer类
        //对字符串s进行遍历
        for (int i = 0;i < s.length();i++){
            char ch = s.charAt(i);
            if (ch == '('){
                stack.push(sb.toString());      //toString()返回序列中的字符串
                sb.setLength(0);                //将字符串置空
            }else if (ch == ')'){
                sb.reverse();                   //字符串反转
                sb.insert(0, stack.pop());
            }else {
                sb.append(ch);                  //追加字符串到此字符串中
            }
        }
        return sb.toString();
    }
}

复杂度

时间复杂度：O（n^2^），其中n是字符串长度。栈的最大深度是O(n)，每一层处理的时间复杂度主要是反转的时间复杂度，为O(n)。

空间复杂度：O(n)，n是字符串长度，在任意时刻，字符串中的任一字符只会被栈中至多一个位置包含一次。

方法二：预处理括号

思路

预处理括号思路图

代码实现

import java.util.*;

public class test{
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.reverseParentheses("(ed(et(oc))el)"));
    }
}

//预处理括号
class Solution{
    public String reverseParentheses(String s){
        int n = s.length();
        int[] pair = new int[n];    //创建整型数组处理括号配对
        Deque<Integer> stack = new LinkedList<Integer>();
        for (int i = 0; i < n;i++){
            if(s.charAt(i) == '('){
                stack.push(i);      //注意压栈的是数组下标
            }else if (s.charAt(i) == ')'){
                /**弹出的栈顶元素是代表左括号赋值给 j，但是当前 i 是右括号
                 * 让右括号指向左括号
                 * 左括号指向右括号
                 * **/
                int j = stack.pop();
                pair[i] = j;
                pair[j] = i;
            }
        }

        StringBuffer sb = new StringBuffer();
        int index = 0, step = 1;
        while (index < n){
            if (s.charAt(index) == '(' || s.charAt(index) == ')'){
                index = pair[index];        //如果是index返回的字符串是左括号，index的值指向右括号，如果是右括号亦然
                step = -step;               //遍历方向反向
            }else {
                sb.append(s.charAt(index));         //是英文字母就加入到字符串str末尾
            }
            index += step;
        }
        return sb.toString();
    }
}

遇到括号就跳转到对应括号后反向遍历，这个方法很巧妙，反转即是逆向的遍历这个思想

输出结果：

leetcode

算法主体

//预处理括号
class Solution{
    public String reverseParentheses(String s){
        int n = s.length();
        int[] pair = new int[n];    //创建整型数组处理括号配对
        Deque<Integer> stack = new LinkedList<Integer>();
        for (int i = 0; i < n;i++){
            if(s.charAt(i) == '('){
                stack.push(i);      //注意压栈的是数组下标
            }else if (s.charAt(i) == ')'){
                /**弹出的栈顶元素是代表左括号赋值给 j，但是当前 i 是右括号
                 * 让右括号指向左括号
                 * 左括号指向右括号
                 * **/
                int j = stack.pop();
                pair[i] = j;
                pair[j] = i;
            }
        }

        StringBuffer sb = new StringBuffer();
        int index = 0, step = 1;
        while (index < n){
            if (s.charAt(index) == '(' || s.charAt(index) == ')'){
                index = pair[index];        //如果是index返回的字符串是左括号，index的值指向右括号，如果是右括号亦然
                step = -step;               //遍历方向反向
            }else {
                sb.append(s.charAt(index));         //是英文字母就加入到字符串str末尾
            }
            index += step;
        }
        return sb.toString();
    }
}