反转每对括号间的子串 图解题解
这道题到底在问什么
- 输入
- s = "(abcd)"
- 输出
- "dcba"（一对括号,整段反转）
- 输入
- s = "(u(love)i)"
- 输出
- "iloveu"（先翻里层 love,再翻外层）
- 输入
- s = "(ed(et(oc))el)"
- 输出
- "leetcode"（三层嵌套）
最优解：一步一步想明白
- 3一句话套路:括号天然是嵌套结构,用栈把「外层还没拼完的片段」存起来,遇到右括号就把内层翻好的片段拼回去。下面一个字符一个字符地走一遍。
- 4开局:当前层片段 cur 为空,栈也是空。指针即将从最左字符开始,逐个读入。栈里存的是「进入括号前还没拼完的外层片段」。
- 5读到第 1 个字符 ( :要进入更深一层括号了。先把当前层已经拼好的片段 cur="空" 压进栈保管。
- 6把 cur="空" 压入栈(成为新栈顶),再把 cur 清空。现在进入内层,cur 重新开始拼。
- 7读到第 2 个字符字母 u :它属于当前层,直接追加到 cur 末尾。
- 8追加后当前层片段 cur="u"。栈不变,继续往右扫下一个字符。
- 9读到第 3 个字符 ( :要进入更深一层括号了。先把当前层已经拼好的片段 cur="u" 压进栈保管。
- 10把 cur="u" 压入栈(成为新栈顶),再把 cur 清空。现在进入内层,cur 重新开始拼。
- 11读到第 4 个字符字母 l :它属于当前层,直接追加到 cur 末尾。
- 12追加后当前层片段 cur="l"。栈不变,继续往右扫下一个字符。
- 13读到第 5 个字符字母 o :它属于当前层,直接追加到 cur 末尾。
- 14追加后当前层片段 cur="lo"。栈不变,继续往右扫下一个字符。
- 15读到第 6 个字符字母 v :它属于当前层,直接追加到 cur 末尾。
- 16追加后当前层片段 cur="lov"。栈不变,继续往右扫下一个字符。
- 17读到第 7 个字符字母 e :它属于当前层,直接追加到 cur 末尾。
- 18追加后当前层片段 cur="love"。栈不变,继续往右扫下一个字符。
- 19读到第 8 个字符 ) :这一层括号结束。先把当前层片段 cur="love" 原地反转。
- 20把这一层片段反转:"love" 变成 "evol"。这就是「从内到外」里当前这一层翻好的结果,马上拼回外层继续。
- 21弹出栈顶的上一层片段 "u",把它接在反转后片段前面,合并成新的 cur="uevol"。这一对括号结算完毕,回到上一层继续。
- 22读到第 9 个字符字母 i :它属于当前层,直接追加到 cur 末尾。
- 23追加后当前层片段 cur="uevoli"。栈不变,继续往右扫下一个字符。
- 24读到第 10 个字符 ) :这一层括号结束。先把当前层片段 cur="uevoli" 原地反转。
- 25把这一层片段反转:"uevoli" 变成 "iloveu"。这一层翻好后,内层早翻好的内容会被再翻一次,正好得到最终顺序。
- 26弹出栈顶的上一层片段 "空",把它接在反转后片段前面,合并成新的 cur="iloveu"。这一对括号结算完毕,回到上一层继续。
- 27整个串扫完,栈已清空,cur="iloveu" 就是最终答案。每对括号都在遇到对应 ) 的那一刻、按从内到外的顺序被反转并拼回,只扫了一遍。
⚠️ 容易写错的地方
✗ 错：遇到 ) 忘了反转就直接拼回
✓ 对：先反转 cur,再接到栈顶后面
右括号的语义就是「把这层内容翻过来」,不反转结果全错
✗ 错：反转后拼接顺序写反
✓ 对：是「栈顶片段 + 反转后片段」
栈顶是外层在括号前的内容,应排在内层翻好的内容前面
✗ 错：遇到 ( 忘了清空 cur
✓ 对：压栈后必须把 cur 重置为空
不清空会让内层把外层字符也算进来,拼出多余内容
✗ 错：想用一次性整体反转代替逐层处理
✓ 对：必须按括号配对逐层结算
嵌套层里的内容会被翻偶数次抵消,单次整体翻无法还原
完整代码（Python / C++ / Java）
Python
class Solution:
def reverseParentheses(self, s: str) -> str:
stack = []
cur = []
for ch in s:
if ch == '(':
stack.append(cur)
cur = []
elif ch == ')':
cur.reverse()
cur = stack.pop() + cur
else:
cur.append(ch)
return ''.join(cur)C++
#include <algorithm>
#include <string>
#include <vector>
using namespace std;
class Solution {
public:
string reverseParentheses(string s) {
vector<string> st;
string cur;
for (char c : s) {
if (c == '(') { st.push_back(cur); cur.clear(); }
else if (c == ')') { reverse(cur.begin(), cur.end()); cur = st.back() + cur; st.pop_back(); }
else cur.push_back(c);
}
return cur;
}
};Java
import java.util.*;
class Solution {
public String reverseParentheses(String s) {
Deque<StringBuilder> st = new ArrayDeque<>();
StringBuilder cur = new StringBuilder();
for (char c : s.toCharArray()) {
if (c == '(') { st.push(cur); cur = new StringBuilder(); }
else if (c == ')') { cur.reverse(); cur = st.pop().append(cur); }
else cur.append(c);
}
return cur.toString();
}
}复杂度
时间
O(n²) 最坏
本栈法每遇 ) 都反转并复制 cur;深层嵌套时同一字符会被多层反复反转复制,最坏到平方级
空间
O(n)
栈与 cur 合计最多存下整个串的字符
可优 O(n)
配对跳转
先记录每个括号的配对位置,再遍历时遇括号就跳到配对处并翻转前进方向,不真正反转任何片段,严格线性
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 反转每对括号间的子串 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么用栈,而不是每遇到一对括号就把子串切出来单独反转?+
切子串反转的写法需要反复定位匹配的括号、复制子串,代码也更碎。用栈则把「外层还没拼完的片段」临时存起来,扫到右括号时弹栈拼回,只需一遍从左到右的扫描就把所有层按正确顺序结算。栈的「后进先出」恰好匹配括号「最内层最先闭合」的嵌套语义,所以反转顺序天然正确;若还想把反转复制的开销也省掉,就用配对跳转那套严格线性的写法。
这题还有没有更优的解法?+
有,而且更优。栈法每遇右括号都要反转并复制片段,深层嵌套时最坏是平方级。更好的是 O(n) 的「括号配对 + 反向跳转」写法:先用一遍扫描记录每个括号的配对位置,再从左到右遍历,遇到括号就跳到它的配对处并翻转前进方向,从而不真正反转任何子串、直接按最终顺序逐字输出。它是严格线性时间,不产生中间片段;做题里能讲清栈法、再点一句这个进阶写法就是加分项。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 反转每对括号间的子串 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。