1190. 反转每对括号间的子串
题目描述
输入字符串 s，只含小写英文字母和括号，括号保证两两配对。
从最内层的括号开始，逐层向外，把每对括号之间的内容整体反转。
返回处理完所有括号后的字符串，结果中不能留下任何括号。
示例 1
输入：s = "(abcd)" 输出："dcba"
解释：把 abcd 反转。
示例 2
输入：s = "(u(love)i)" 输出："iloveu"
解释：先反转 love 得到 evol，再反转整个 uevoli。
示例 3
输入：s = "(ed(et(oc))el)" 输出："leetcode"
解释：依次反转 oc、etco，最后反转整串。
数据范围
1 <= s.length <= 2000s只含小写英文字母和括号。- 保证所有括号都成对出现。
解题思路：栈模拟
括号嵌套就是栈的结构。栈中每一层是一个正在收集的字符列表，最底层是外面的结果。遇到 ( 就开一个新层；遇到字母就加到栈顶层；遇到 ) 说明当前层已经是一对括号内的完整内容（它更里面的括号已经处理好），把它弹出、反转，接到下面一层的末尾。
为什么正确
栈的层数 = 当前未闭合的左括号数 + 1；每层保存的是该括号内已经完成内层反转的内容。
复杂度分析
时间最坏 O(n^2)（每层弹出时要复制反转），n <= 2000 足够；空间 O(n)。
易错点
不要先处理最外层：反转必须从内到外。用栈时遇到 ) 弹出的一定是最内层，顺序自然正确。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def reverseParentheses(self, s: str) -> str:
stack = [[]]
for c in s:
if c == '(':
stack.append([])
elif c == ')':
inner = stack.pop()
stack[-1].extend(reversed(inner))
else:
stack[-1].append(c)
return ''.join(stack[0])class Solution {
public String reverseParentheses(String s) {
Deque<StringBuilder> stack = new ArrayDeque<>();
stack.push(new StringBuilder());
for (char c : s.toCharArray()) {
if (c == '(') {
stack.push(new StringBuilder());
} else if (c == ')') {
StringBuilder inner = stack.pop();
stack.peek().append(inner.reverse());
} else {
stack.peek().append(c);
}
}
return stack.peek().toString();
}
}class Solution {
public:
string reverseParentheses(string s) {
vector<string> stack(1);
for (char c : s) {
if (c == '(') {
stack.push_back("");
} else if (c == ')') {
string inner = stack.back(); stack.pop_back();
stack.back().append(inner.rbegin(), inner.rend());
} else {
stack.back().push_back(c);
}
}
return stack[0];
}
};func reverseParentheses(s string) string {
stack := [][]byte{{}}
for i := 0; i < len(s); i++ {
c := s[i]
if c == '(' {
stack = append(stack, []byte{})
} else if c == ')' {
inner := stack[len(stack)-1]
stack = stack[:len(stack)-1]
for j := len(inner) - 1; j >= 0; j-- {
stack[len(stack)-1] = append(stack[len(stack)-1], inner[j])
}
} else {
stack[len(stack)-1] = append(stack[len(stack)-1], c)
}
}
return string(stack[0])
}var reverseParentheses = function(s) {
const stack = [[]];
for (const c of s) {
if (c === '(') {
stack.push([]);
} else if (c === ')') {
const inner = stack.pop();
stack[stack.length - 1].push(...inner.reverse());
} else {
stack[stack.length - 1].push(c);
}
}
return stack[0].join('');
};function reverseParentheses(s: string): string {
const stack: string[][] = [[]];
for (const c of s) {
if (c === '(') {
stack.push([]);
} else if (c === ')') {
const inner = stack.pop()!;
stack[stack.length - 1].push(...inner.reverse());
} else {
stack[stack.length - 1].push(c);
}
}
return stack[0].join('');
}其他解法
栈模拟每闭合一层括号就把内容反转一次，嵌套深时会反复翻转同一段字符，最坏 O(n²)；配对跳转法通过改变读取方向代替真正的翻转，只扫描一遍。
解法 2：预处理括号配对 + 反向遍历 时间 O(n)，空间 O(n)
先用栈求出每个括号对应的另一半的位置 pair。然后从左到右遍历，遇到普通字符就加入答案；遇到括号时跳到它配对的括号处，并把遍历方向反过来。这相当于进入一层括号时从另一端往回读，读完这层后再跳回来恢复原方向。每个字符恰好被访问一次。
不需要反复翻转字符串，严格线性时间，嵌套很深时优势明显。跳转加换向的正确性不太直观，需要手工模拟一遍才能理解。
class Solution:
def reverseParentheses(self, s: str) -> str:
n = len(s)
pair = [0] * n
stack = []
for i, c in enumerate(s):
if c == '(':
stack.append(i)
elif c == ')':
j = stack.pop()
pair[i], pair[j] = j, i
res = []
i, step = 0, 1
while i < n:
if s[i] in '()':
i = pair[i]
step = -step
else:
res.append(s[i])
i += step
return ''.join(res)class Solution {
public String reverseParentheses(String s) {
int n = s.length();
int[] pair = new int[n];
Deque<Integer> stack = new ArrayDeque<>();
for (int i = 0; i < n; i++) {
if (s.charAt(i) == '(') {
stack.push(i);
} else if (s.charAt(i) == ')') {
int j = stack.pop();
pair[i] = j;
pair[j] = i;
}
}
StringBuilder res = new StringBuilder();
for (int i = 0, step = 1; i < n; i += step) {
char c = s.charAt(i);
if (c == '(' || c == ')') {
i = pair[i];
step = -step;
} else {
res.append(c);
}
}
return res.toString();
}
}class Solution {
public:
string reverseParentheses(string s) {
int n = s.size();
vector<int> pair(n), stk;
for (int i = 0; i < n; i++) {
if (s[i] == '(') {
stk.push_back(i);
} else if (s[i] == ')') {
int j = stk.back();
stk.pop_back();
pair[i] = j;
pair[j] = i;
}
}
string res;
for (int i = 0, step = 1; i < n; i += step) {
if (s[i] == '(' || s[i] == ')') {
i = pair[i];
step = -step;
} else {
res += s[i];
}
}
return res;
}
};func reverseParentheses(s string) string {
n := len(s)
pair := make([]int, n)
stack := []int{}
for i := 0; i < n; i++ {
if s[i] == '(' {
stack = append(stack, i)
} else if s[i] == ')' {
j := stack[len(stack)-1]
stack = stack[:len(stack)-1]
pair[i], pair[j] = j, i
}
}
res := []byte{}
for i, step := 0, 1; i < n; i += step {
if s[i] == '(' || s[i] == ')' {
i = pair[i]
step = -step
} else {
res = append(res, s[i])
}
}
return string(res)
}var reverseParentheses = function(s) {
const n = s.length;
const pair = new Array(n).fill(0);
const stack = [];
for (let i = 0; i < n; i++) {
if (s[i] === '(') {
stack.push(i);
} else if (s[i] === ')') {
const j = stack.pop();
pair[i] = j;
pair[j] = i;
}
}
const res = [];
for (let i = 0, step = 1; i < n; i += step) {
if (s[i] === '(' || s[i] === ')') {
i = pair[i];
step = -step;
} else {
res.push(s[i]);
}
}
return res.join('');
};function reverseParentheses(s: string): string {
const n = s.length;
const pair: number[] = new Array(n).fill(0);
const stack: number[] = [];
for (let i = 0; i < n; i++) {
if (s[i] === '(') {
stack.push(i);
} else if (s[i] === ')') {
const j = stack.pop()!;
pair[i] = j;
pair[j] = i;
}
}
const res: string[] = [];
for (let i = 0, step = 1; i < n; i += step) {
if (s[i] === '(' || s[i] === ')') {
i = pair[i];
step = -step;
} else {
res.push(s[i]);
}
}
return res.join('');
}