LeetCode 1190. Reverse Substrings Between Each Pair of Parentheses

题意

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

例子:

"(abcd)"
反转之后就是:
cdba
"(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));
                }
            }
        }
    }
}

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.