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

约 5 分钟
文章信息 9 个分类 2 个标签
分类
LeetCode CodeTop 中等 未解决 2-5 腾讯 字节 华为 微软
标签
字符串 栈

题目描述

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

image-20260928230259503

image-20260928230259504

题意分析

字符串包含小写字母和成对匹配的括号，需要从内到外反转每对括号内部的内容，最终返回去掉所有括号后的字符串。

一个字符可能位于多层括号中，会受到多次反转影响。相邻括号段各自处理，嵌套段则先形成内层结果再参与外层反转，不能仅根据字符所在层数决定它的最终位置。

解法：括号配对后改变遍历方向

核心思路

[!blue]

反转一段内容，可以通过从它的另一端朝相反方向读取来实现，无需真正搬动字符。先记录每一对括号的下标关系，再用当前下标 idx 和方向 dir 控制读取路径，dir = 1 表示向右，-1 表示向左。

从某一侧遇到括号，说明要进入或离开这一对括号管理的区间。把 idx 跳到配对括号，令方向取反，再按新方向走一步，就会从另一端以相反顺序读取内部内容，或在内部完成后回到外层继续读取。

对嵌套括号使用同一规则即可。外层已经改变了进入内层的方向，内层再跳到自己的另一端并掉头，相当于在外层读取顺序上再做一次反转。这正好对应内层处理后又参与外层反转的效果，所以不需要显式复制每一层的中间字符串。

配对表必须双向保存，因为遍历可能向左，也就可能先遇到右括号。字母按当前方向直接加入答案，括号只负责跳转，不加入结果。跳转后仍要执行统一的 idx += dir，否则会停在配对括号上反复跳转。

每对括号在进入和离开其区间时各触发一次跳转，每个字母只输出一次。最终走出整个字符串范围时，所有内容都已按正确方向读取完成。

解题步骤

  1. 从左到右扫描，用栈保存尚未匹配的左括号下标。
  2. 遇到右括号时弹出对应左括号，同时登记两端互相指向的 pair 值。
  3. 从下标 0、方向 1 开始遍历。
  4. 遇到字母就追加结果；遇到任意括号就跳到配对位置，并把方向取反。
  5. 两种分支结束后都按当前方向移动一格，直到下标越过字符串边界，返回结果。

代码实现

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)$，建立配对表扫描一次；正式读取时每个字母输出一次，每对括号只触发常数次跳转。
  • 空间复杂度：$O(n)$，保存括号配对、未匹配下标栈和结果缓冲区。

关键点总结

[!green]

  • 用改变读取方向代替移动字符，把重复的区间反转转成线性遍历。
  • 配对关系确定反转的范围，当前方向表示此前外层反转的影响，两者必须一起使用。
  • 跳转、方向取反、按新方向移动三步配套，才能正确进入内部或返回外层。

易错点总结

[!yellow]

  • 只跳到另一端却不改变方向，会跳过应当反向读取的内容。
  • 掉头后不继续移动，会立即再次处理配对括号，陷入来回跳转。
  • 只记录左括号到右括号，向左遍历先碰到右括号时就无法跳回。
  • 把括号追加到结果，不符合最终只保留字母的要求。
  • 每遇到右括号就实际复制反转整个内部字符串，在深层嵌套时可能让同一字符反复搬动，失去本写法的线性复杂度。

相似题目

题目 难度 关联与区别
394. 字符串解码 中等 同样处理嵌套括号，本题逆序内部字符而不是重复；逐层反复复制可能造成额外开销。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/76749252
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！