LC 1190. 反转每对括号间的子串
题目描述
这是 LeetCode 上的 1190. 反转每对括号间的子串 ,难度为 中等。
给出一个字符串 s
(仅含有小写英文字母和括号)。
请你按照从括号内到外的顺序,逐层反转每对匹配括号中的字符串,并返回最终的结果。
注意,您的结果中 不应 包含任何括号。
示例 1:1
2
3输入:s = "(abcd)"
输出:"dcba"
示例 2:1
2
3输入:s = "(u(love)i)"
输出:"iloveu"
示例 3:1
2
3输入:s = "(ed(et(oc))el)"
输出:"leetcode"
示例 4:1
2
3输入:s = "a(bcdefghijkl(mno)p)q"
输出:"apmnolkjihgfedcbq"
提示:
- $0 <= s.length <= 2000$
s
中只有小写英文字母和括号- 我们确保所有括号都是成对出现的
双端队列
根据题意,我们可以设计如下处理流程:
- 从前往后遍历字符串,将不是
)
的字符串从「尾部」放入队列中 - 当遇到
)
时,从队列「尾部」取出字符串,直到遇到(
为止,并对取出字符串进行翻转 - 将翻转完成后字符串重新从「尾部」放入队列
- 循环上述过程,直到原字符串全部出来完成
- 从队列「头部」开始取字符,得到最终的答案
可以发现,上述过程需要用到双端队列(或者栈,使用栈的话,需要在最后一步对取出字符串再进行一次翻转)。
在 Java
中,双端队列可以使用自带的 ArrayDeque
, 也可以直接使用数组进行模拟。
代码(使用 ArrayDeque
):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
27class Solution {
public String reverseParentheses(String s) {
int n = s.length();
char[] cs = s.toCharArray();
Deque<Character> d = new ArrayDeque<>();
for (int i = 0; i < n; i++) {
char c = cs[i];
if (c == ')') {
StringBuilder path = new StringBuilder();
while (!d.isEmpty()) {
if (d.peekLast() != '(') {
path.append(d.pollLast());
} else {
d.pollLast();
for (int j = 0; j < path.length(); j++) d.addLast(path.charAt(j));
break;
}
}
} else {
d.addLast(c);
}
}
StringBuilder sb = new StringBuilder();
while (!d.isEmpty()) sb.append(d.pollFirst());
return sb.toString();
}
}
代码(数组模拟双端队列):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
27class Solution {
int N = 2010, he = 0, ta = 0;
char[] d = new char[N], path = new char[N];
public String reverseParentheses(String s) {
int n = s.length();
char[] cs = s.toCharArray();
for (int i = 0; i < n; i++) {
char c = cs[i];
if (c == ')') {
int idx = 0;
while (he < ta) {
if (d[ta - 1] == '(' && --ta >= 0) {
for (int j = 0; j < idx; j++) d[ta++] = path[j];
break;
} else {
path[idx++] = d[--ta];
}
}
} else {
d[ta++] = c;
}
}
StringBuilder sb = new StringBuilder();
while (he < ta) sb.append(d[he++]);
return sb.toString();
}
}
- 时间复杂度:每个
(
字符只会进出队列一次;)
字符串都不会进出队列,也只会被扫描一次;分析的重点在于普通字符,可以发现每个普通字符进出队列的次数取决于其右边的)
的个数,最坏情况下每个字符右边全是右括号,因此复杂度可以当做 $O(n^2)$,但实际计算量必然取不满 $n^2$,将普通字符的重复弹出均摊到整个字符串处理过程,可以看作是每个字符串都被遍历常数次,复杂度为 $O(n)$ - 空间复杂度:$O(n)$
最后
这是我们「刷穿 LeetCode」系列文章的第 No.1190
篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先把所有不带锁的题目刷完。
在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:https://github.com/SharingSource/LogicStack-LeetCode 。
在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!