LeetCode 1190. 反转每对括号间的子串
目录
题目描述
题意分析
给一个由小写字母和括号组成的字符串
s，题目保证括号是成对且合法嵌套的。要求从最内层开始，逐层把每对括号里的内容反转，最终返回一个不含任何括号的结果串。「保证括号合法」这个前提值得先记下：它意味着不需要做任何合法性校验，每个左括号都一定能找到唯一配对的右括号，可以放心地依赖配对关系。
关键要看清嵌套带来的效应。一个字母如果被
k层括号包住，它就会被反转k次；反转两次等于没反转，所以最终每个字母的相对位置只取决于包裹它的括号层数的奇偶性。这解释了为什么不能偷懒：先把所有括号删掉再把整串反转一次是错的，因为不同字母的嵌套深度不同，它们受到的反转次数并不一致。「从最内层开始逐层反转」这句话看似规定了执行顺序，其实是在描述结果的定义。真正需要的能力有两个：一是知道每个左括号和哪个右括号配对，从而界定每一层的范围；二是有办法把「反转」这个动作表达出来，而不必真的一次次去翻转字符串。
字符串长度是两千量级，这个规模并不逼人——朴素地每遇到一个右括号就把当前累积的片段原地翻转，最坏是平方级但仍能通过。不过题目本身给了一个更漂亮的线性解，也是面试里更容易被追问到的那一层。
边界：串里可能一个括号都没有，此时原样返回；也可能出现空的括号对，比如
()，反转空串仍是空串，答案里不该留下任何痕迹。
解法：括号配对后改变遍历方向
核心思路
朴素做法是用一个栈存放「还没结算的片段」：遇到左括号就把当前片段压栈并另起一段，遇到右括号就把当前段翻转后接回栈顶那段。它正确且好写，但每次
reverse都要真的搬运字符，嵌套很深时同一批字符会被反复翻来翻去。瓶颈在于「反转」被当成了一个需要物理执行的动作。换个角度观察：反转一段区间，等价于从右往左读这段区间。既然如此，与其搬字符，不如让读取的方向本身发生变化——遇到括号时不真的翻转内容，而是掉头，从另一端开始读。
具体到实现：先预处理出
pair数组，pair[i]表示下标i处的括号所配对的另一个括号的下标，左右双向都要记。这一步用一个栈线性完成，遇到(压下标，遇到)弹出栈顶得到配对的左括号位置，两边互相登记。然后用一个游标
idx和一个方向量dir（+1表示向右读，-1表示向左读）扫描原串，从idx = 0、dir = +1出发。规则只有两条：碰到字母就把它追加进答案；碰到括号（无论左右）就idx = pair[idx]跳到配对括号处，同时dir = -dir掉头。两条规则处理完之后统一执行一次idx += dir迈出一步。这个规则为什么对：向右读时遇到
(，说明即将进入一段需要反转的区间，反转后应该从这段的末尾往回读，而这段的末尾正是配对的)，跳过去并掉头正是这个意思；向左读时遇到)，同理是要从配对的(之后向右读。两种情形被同一行代码统一处理，这正是这个解法优雅的地方。不变量是：游标每一步落在的位置，恰好是「答案串中下一个字符」在原串里的来源位置；每个括号在整个过程中被经过且仅被经过两次（一次从外侧进入、一次从内侧返回），每个字母被经过且仅被经过一次，所以扫描总步数是线性的，不会打转。
解题步骤
- 建立配对数组：开一个长度为
n的pair，用栈扫一遍原串，遇到(把下标压栈，遇到)弹出栈顶left，同时写入pair[left] = i和pair[i] = left。为什么必须双向登记：游标既可能从左侧撞到(，也可能从右侧撞到)，两个方向都要能一步跳到对面，只记单向会让反向跳转读到默认值0。- 初始化游标：
idx = 0、dir = 1。为什么从最左端向右：最外层不在任何括号里，嵌套深度为 0，不需要反转，自然是正序读。- 循环条件
idx >= 0 && idx < n：为什么两端都判。向右走到底会自然越过右端，这是正常出口；左端的判断是防御性的——合法括号结构下游标向左移动时必定会先撞到某个左括号并被弹回，理论上不会走到负下标，但把条件写全能让代码对非法输入也不至于抛异常。- 遇到括号则跳转加掉头：
idx = pair[idx]、dir = -dir。为什么先跳再掉头的顺序无所谓，但两件事一件都不能少：只跳不掉头会原地打转般地在括号对之间来回穿梭，只掉头不跳则根本没进入正确的区间。- 遇到字母则追加到结果，括号本身永远不追加。为什么：题目要求结果不含括号，括号只承担控制流的角色。
- 统一执行
idx += dir：为什么要放在分支外面、跳转之后还要再走一步。跳转只是把游标搬到配对括号所在的位置，那个位置上仍然是一个括号，若不再迈一步就会在下一轮重新触发跳转，两个括号之间无限互跳。- 返回结果串，Java 用
StringBuilder累积、Go 用[]byte累积，避免不可变字符串反复拷贝。以
s = "(u(love)i)"走一遍。下标依次是0:'('、1:'u'、2:'('、3:'l'、4:'o'、5:'v'、6:'e'、7:')'、8:'i'、9:')'。预处理阶段：扫到下标 0 的
(压栈；下标 2 的(压栈；下标 7 的)弹出栈顶 2，登记pair[2] = 7、pair[7] = 2；下标 9 的)弹出栈顶 0，登记pair[0] = 9、pair[9] = 0。
idx = 0、dir = 1，字符是(：跳到pair[0] = 9，dir变成-1，走一步到idx = 8。含义是最外层要反转，于是从末尾往回读。
idx = 8，字符i：追加，答案变成"i"；idx += -1到7。
idx = 7，字符)：跳到pair[7] = 2，dir由-1变回+1，走一步到idx = 3。含义是内层括号被外层反转过一次、自身再反转一次，两次抵消，回到正序读。
idx = 3, 4, 5, 6，依次是l、o、v、e：全部追加，答案变成"ilove"；游标推进到idx = 7。
idx = 7，字符)：再次跳到pair[7] = 2，dir变成-1，走一步到idx = 1。这是从内层区间的另一端退出，注意下标 7 这个括号一共只被经过两次，符合前面说的不变量。
idx = 1，字符u：追加，答案变成"iloveu"；idx += -1到0。
idx = 0，字符(：跳到pair[0] = 9，dir变回+1，走一步到idx = 10。此时idx >= n，循环退出。返回
"iloveu"。用定义验算一遍：内层(love)反转成evol，外层变成(u evol i)，再反转得到i love u，即iloveu，一致。顺带看两个错误写法的后果。若跳转后忘了
idx += dir，在idx = 0跳到9、掉头之后，下一轮又从9跳回0、再掉头，游标在这两个下标之间无限往返，程序死循环。若pair只记录了pair[left] = right而没记反向，那么走到idx = 7时读到的pair[7]是默认值0，游标会跳到最外层左括号，答案彻底错乱。
代码实现
class Solution {
public String reverseParentheses(String s) {
int n = s.length();
int[] pair = new int[n];
int[] stack = new int[n];
int top = 0;
for (int i = 0; i < n; i++) {
char ch = s.charAt(i);
if (ch == '(') {
stack[top++] = i;
} else if (ch == ')') {
int left = stack[--top];
pair[left] = i;
pair[i] = left;
}
}
StringBuilder ans = new StringBuilder();
int idx = 0;
int dir = 1;
while (idx >= 0 && idx < n) {
char ch = s.charAt(idx);
if (ch == '(' || ch == ')') {
// 跳到配对括号并反向移动，相当于进入一段反转区间。
idx = pair[idx];
dir = -dir;
} else {
ans.append(ch);
}
idx += dir;
}
return ans.toString();
}
}
func reverseParentheses(s string) string {
n := len(s)
pair := make([]int, n)
stack := make([]int, 0, n)
for i := 0; i < n; i++ {
if s[i] == '(' {
stack = append(stack, i)
} else if s[i] == ')' {
left := stack[len(stack)-1]
stack = stack[:len(stack)-1]
pair[left] = i
pair[i] = left
}
}
res := make([]byte, 0, n)
idx := 0
dir := 1
for idx >= 0 && idx < n {
if s[idx] == '(' || s[idx] == ')' {
// 跳到配对括号并反向移动，相当于进入一段反转区间。
idx = pair[idx]
dir = -dir
} else {
res = append(res, s[idx])
}
idx += dir
}
return string(res)
}
复杂度分析
- 时间复杂度：$O(n)$。预处理配对是一次线性扫描，栈的压入弹出总次数不超过括号个数；主循环里每个字母恰好被访问一次、每个括号恰好被访问两次（外侧进入一次、内侧退出一次），总步数不超过 $2n$，且没有任何字符串反转操作。
- 空间复杂度：$O(n)$。
pair数组与括号栈各占线性空间，结果缓冲区也是线性的。相比每遇右括号就reverse的栈式写法，本解法用一份下标映射换掉了反复的字符搬运，最坏情况从平方级降到线性。
关键点总结
- 「反转一段区间」和「从右往左读这段区间」是等价的，把物理操作换成读取方向的翻转，是处理嵌套反转类问题的通用降复杂度手法。
- 括号配对下标（
pair数组）是括号类题目的通用中间产物，用一个栈即可线性构造；一旦拿到它，很多看似需要递归的问题都能改写成一次带跳转的线性扫描。- 嵌套深度的奇偶性决定字符最终是否被反转，这条结论能立刻否掉「先删括号再整体反转」之类的错误捷径，面试里主动举出反例比直接写代码更能体现分析能力。
- 跳转与掉头必须成对出现，且之后仍要照常迈一步，三个动作缺一不可；把
idx += dir提到分支外统一执行，正是为了保证这一点不被遗漏。- 面试时可以先给出栈式解法说明思路正确，再主动指出它在深嵌套下的反转开销，然后引出这个线性解——「先给可行解再给最优解」的展开方式通常比一上来就写巧解更稳。
易错点总结
- 跳转后忘记
idx += dir（比如写成continue）："(abc)"中游标从 0 跳到 4、掉头，下一轮又从 4 跳回 0、再掉头，在两个括号间无限往返，程序死循环。- 跳转时忘记
dir = -dir："(abc)"中游标从 0 跳到 4 后仍向右走，直接迈到下标 5 退出循环，返回空串而不是"cba"。dir = -dir误写成dir = -1："(ab)(cd)"中第一对括号处理完后方向被钉死在-1，游标在下标 0 到 3 之间来回跳，永远走不到第二对括号，死循环。pair只记录pair[left] = right，不记反向："(u(love)i)"中游标向左撞到下标 7 的)时读到默认值0，跳回最外层左括号，输出重复且错乱的结果。- 把括号也追加进结果：
"(abc)"会输出带括号的串，而题目明确要求结果中不含括号。- 先删掉所有括号再把整串反转一次：
"(u(love)i)"会得到"ievolu"，正确答案是"iloveu"；深度为偶数的字符本不该被反转。- 忽略嵌套深度，只反转最外层一次：
"(ed(et(oc))el)"的正确答案是"leetcode"，只反转一层会把内层的oc、et留在错误顺序上。- 弹栈前不确认栈非空：本题保证括号合法所以不会触发，但把同一份代码复制到括号可能非法的题目上，
stack[--top]会得到负下标并抛出越界异常。- 结果用
String做+=拼接：每次拼接都要复制整条已有结果，长串下退化成平方级的字符拷贝，白白浪费掉这个解法省下来的开销。- 循环条件只写
idx < n：向左移动时若因为其它 bug 走到负下标，s.charAt(-1)会直接抛异常而不是安静退出，排查起来比写全条件麻烦得多。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 394. 字符串解码 | 中等 | 括号前带重复次数，栈里要同时保存数字和已拼好的片段 |
| 20. 有效的括号 | 简单 | 只判断配对是否合法，不产出内容，是配对栈的最小模型 |
| 856. 括号的分数 | 中等 | 同样依赖嵌套结构，但合并规则是加倍求和而不是拼接字符 |
| 1614. 括号的最大嵌套深度 | 简单 | 只需一个深度计数器，连配对下标都不用记 |
| 32. 最长有效括号 | 困难 | 括号不保证合法，用下标栈求最长合法区间长度 |
| 1249. 移除无效的括号 | 中等 | 需要先标记出无法配对的括号再删除，考的是不合法情形的处理 |
| 224. 基本计算器 | 困难 | 括号内是表达式，符号随嵌套层数取反，与本题的方向取反完全同构 |
| 726. 原子的数量 | 困难 | 括号带倍数，需要把内层计数整体乘上系数再向外合并 |
| 1047. 删除字符串中的所有相邻重复项 | 简单 | 栈的基础消除模型，没有嵌套结构也无需配对下标 |
| 735. 小行星碰撞 | 中等 | 同样用栈处理带方向的元素，方向决定的是碰撞而非读取顺序 |