JZX轻语：简

LeetCode 1190 - 反转每对括号间的子串

发表于2024年07月05日

#栈 #字符串

本质就是将括号里面的字符串反转，由于括号支持嵌套的，即可能会有多次的翻转操作。直观的做法就是先将最里层的括号里面的字符串反转，然后再将外层的括号里面的字符串反转，以此类推。可以使用一个数组来维护上述的层次信息：如果遇到左括号，则说明有新的层次，新建一层推入到数组中；如果遇到字符，则将字符加入到最顶层的字符串中；如果遇到右括号，意味着层次结束，则将当前层的字符串反转后加入到上一层的字符串中，并将当前层弹出。最终返回数组的第一层即可。不难看到，这个层次信息数组本质就是个栈。

其实，遇到这种带括号的字符串题，首先应该想到栈的解法。只不过得想清楚栈要怎么用。

class Solution:
    def reverseParentheses(self, s: str) -> str:
        stacks = [[]]
        for ch in s:
            if ch == '(':
                stacks.append([])
            elif ch == ')':
                popped_level_stack = stacks.pop()
                stacks[-1].extend(reversed(popped_level_stack))
            else:
                stacks[-1].append(ch)
        return ''.join(stacks[0])

闪念标签：LC

题目链接：https://leetcode.cn/problems/reverse-substrings-between-each-pair-of-parentheses/