What is the main pattern used in Reverse Substrings Between Each Pair of Parentheses?

The problem relies on stack-based state management to track characters inside nested parentheses and reverse them efficiently.

Can this approach handle multiple nested parentheses?

Yes, using a stack ensures that innermost parentheses are reversed first, maintaining the correct order for all nested levels.

Do we need to remove the parentheses in the output?

Yes, after reversing substrings, all parentheses should be removed to produce the final string containing only letters.

What is the time complexity of this solution?

The solution runs in O(n) time since each character is pushed and popped from the stack at most once.

What common mistakes should I avoid in this problem?

Avoid reversing the entire string at once, mishandling nested parentheses, or leaving parentheses in the final output.

#1190

Medium

auto_awesome栈·状态

LeetCode 题解工作台

反转每对括号间的子串

给出一个字符串 s （仅含有小写英文字母和括号）。请你按照从括号内到外的顺序，逐层反转每对匹配括号中的字符串，并返回最终的结果。注意，您的结果中不应包含任何括号。示例 1：输入： s = "(abcd)" 输出： "dcba" 示例 2：输入： s = "(u(love)i)" 输出：…

字符串栈

题目描述

给出一个字符串 s（仅含有小写英文字母和括号）。

请你按照从括号内到外的顺序，逐层反转每对匹配括号中的字符串，并返回最终的结果。

注意，您的结果中不应包含任何括号。

示例 1：

输入：s = "(abcd)"
输出："dcba"

示例 2：

输入：s = "(u(love)i)"
输出："iloveu"
解释：先反转子字符串 "love" ，然后反转整个字符串。

示例 3：

输入：s = "(ed(et(oc))el)"
输出："leetcode"
解释：先反转子字符串 "oc" ，接着反转 "etco" ，然后反转整个字符串。

提示：

1 <= s.length <= 2000
s 中只有小写英文字母和括号
题目测试用例确保所有括号都是成对出现的

lightbulb

解题思路

方法一：模拟

我们可以直接用栈来模拟反转的过程。

时间复杂度 $O(n^2)$ ，空间复杂度 $O(n)$ ，其中 $n$ 为字符串 $s$ 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class Solution:
    def reverseParentheses(self, s: str) -> str:
        stk = []
        for c in s:
            if c == ")":
                t = []
                while stk[-1] != "(":
                    t.append(stk.pop())
                stk.pop()
                stk.extend(t)
            else:
                stk.append(c)
        return "".join(stk)

speed

复杂度分析

指标	值
时间	complexity is O(n) because each character is pushed and popped at most once. Space complexity is O(n) due to the stack storing all characters and intermediate substrings for nested parentheses.
空间	O(n)

psychology

面试官常问的追问

外企场景

question_mark
Ask about handling nested parentheses and reversing inner substrings first.
question_mark
Check understanding of stack-based state management for string transformations.
question_mark
Expect explanation of why reversing at the closing parenthesis ensures correct output.

warning

常见陷阱

外企场景

error
Failing to reverse only the substring within the current pair of parentheses.
error
Ignoring nested parentheses and reversing the string globally too early.
error
Not removing the parentheses from the final output, resulting in incorrect formatting.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Instead of reversing, rotate characters within each parentheses segment.
arrow_right_alt
Use a queue instead of a stack to explore alternative traversal strategies.
arrow_right_alt
Handle additional characters like digits or punctuation while reversing substrings.

help

常见问题

外企场景

继续练习

#1209 删除字符串中的所有相邻重复项 II #1249 移除无效的括号 #1111 有效括号的嵌套深度