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)(遍历两遍字符串数组)。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
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));
}
}
}
}
}

LeetCode 1190. Reverse Substrings Between Each Pair of Parentheses

https://www.robberphex.com/reverse-substrings-between-each-pair-of-parentheses/

作者

Robert Lu

发布于

2019-09-19

许可协议

评论