---

1190. 反转每对括号间的子串

• 标签：栈、字符串
• 难度：中等

题目链接

• 1190. 反转每对括号间的子串 - 力扣

题目大意

描述：给定一个字符串 $s$（仅含有小写英文字母和括号）。

要求：按照从括号内到外的顺序，逐层反转每对匹配括号中的子串，并返回最终的结果。结果中不应包含任何括号。

说明：

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

示例：

• 示例 1：

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

• 示例 2：

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

• 示例 3：

输入：s = "(ed(et(oc))el)"
输出："leetcode"

解题思路

思路 1：栈

为什么用栈？ 因为括号嵌套的特点是"后遇到的左括号先闭合"，这和栈的后进先出完全吻合。每个左括号对应栈里的一层，右括号闭合时弹出这一层处理。

拆解步骤：

1. 初始化栈：压入一个空字符串 ['']。

2. 遍历每个字符：

   • 遇到 (：压入一个新的空字符串，表示新的一层
   • 遇到字母：追加到栈顶字符串的末尾
   • 遇到 )：弹出栈顶字符串，反转后追加到新的栈顶字符串末尾

3. 返回栈底的字符串。

用人话举个例子：s = "(u(love)i)"

• 初始：['']
• 遇到 (：['', '']
• 遇到 u：['', 'u']
• 遇到 (：['', 'u', '']
• 遇到 love：['', 'u', 'love']
• 遇到 )：弹出 'love' 反转成 'evol'，追加到上一层 → ['', 'uevol']
• 遇到 i：['', 'uevoli']
• 遇到 )：弹出 'uevoli' 反转成 'iloveu'，追加到上一层 → ['iloveu']
• 结果："iloveu"

思路 1：代码

class Solution:
    def reverseParentheses(self, s: str) -> str:
        # 栈里存字符串，初始有一个空字符串
        stack = ['']

        for ch in s:
            if ch == '(':
                # 遇到左括号，压入新的空字符串，开始新的一层
                stack.append('')
            elif ch == ')':
                # 遇到右括号，弹出当前层并反转，合并到上一层
                top = stack.pop()
                stack[-1] += top[::-1]
            else:
                # 遇到字母，直接追加到当前层的末尾
                stack[-1] += ch

        return stack[0]

思路 1：复杂度分析

• 时间复杂度：$O(n^2)$。用人话说就是：最坏情况下（如 "(((a)))"），每遇到一个 ) 就要反转一次字符串，反转操作需要 $O(n)$ 时间，可能反转 $O(n)$ 次。
• 空间复杂度：$O(n)$。栈中存储的字符串总长度不超过原字符串长度。