LeetCode 1190. Reverse Substrings Between Each Pair of Parentheses

题意

每层括号里面的东西需要反转一次。即在在偶数层括号里面的字符是正序的，在奇数层括号里面的字符是逆序的。然后拼成结果。

例子：

“(abcd)”
反转之后就是：
dcba

“(u(love)i)”
love不反转，u,love,i三个反转，答案为：
iloveu

思路

网上有人直接用栈存储，每一个元素代表当前层级括号中的字符串，如果遇到括号关闭，将当前层级字符串反转再append到上一级的字符串中。

但是，括号层级一多，字符串反转的次数就非常多了。而且很多反转都是没有必要的。

其实直接递归就好，或者说分治：

每个括号内部都算作独立的子问题，如果正序，直接逐个append，逆序则反向append；如果遇到括号，则继续分治。

这样空间复杂度O(n)（取决于多少括号），时间复杂度O(n)（遍历两遍字符串数组）。

代码

import java.util.Stack;

class Solution {
    private int[] parent;

    public String reverseParentheses(String s) {
        parent = new int[s.length()];
        Stack<Integer> stack = new Stack<Integer>();
        for (int i = 0; i < s.toCharArray().length; i++) {
            if (s.charAt(i) == '(') {
                stack.push(i);
            } else if (s.charAt(i) == ')') {
                int f = stack.pop();
                parent[f] = i;
                parent[i] = f;
            }
        }
        StringBuilder sb = new StringBuilder(s.length());
        reverse(s, 0, s.length() - 1, false, sb);
        return sb.toString();
    }

    private void reverse(String s, int start, int end, boolean reversed, StringBuilder sb) {
        if (reversed) {
            for (int i = end; i >= start; i--) {
                if (s.charAt(i) == ')') {
                    reverse(s, parent[i] + 1, i - 1, false, sb);
                    i = parent[i];
                } else {
                    sb.append(s.charAt(i));
                }
            }
        } else {
            for (int i = start; i <= end; i++) {
                if (s.charAt(i) == '(') {
                    reverse(s, i + 1, parent[i] - 1, true, sb);
                    i = parent[i];
                } else {
                    sb.append(s.charAt(i));
                }
            }
        }
    }
}