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

Categories:

题目描述
思路分析
1. 解法一：括号配对 + 方向遍历（推荐）
相似题目

题目描述

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

思路分析

解法一：括号配对 + 方向遍历（推荐）

核心思路：

先用栈找到每个括号的配对位置 pair[i]。

从左到右遍历字符串，当遇到括号就跳转到配对位置并反转方向。

只在方向为正向时追加字符，整体复杂度为 O(n)。

复杂度分析：

时间复杂度：O(n)，其中 n 表示字符串长度。

空间复杂度：O(n)，用于栈与配对数组。

import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
    public String reverseParentheses(String s) {
        int n = s.length();
        int[] pair = new int[n];
        Deque<Integer> stack = new ArrayDeque<>();

        // 预处理每个括号的配对位置
        for (int i = 0; i < n; i++) {
            char ch = s.charAt(i);
            if (ch == '(') {
                stack.push(i);
            } else if (ch == ')') {
                int j = stack.pop();
                pair[i] = j;
                pair[j] = i;
            }
        }

        StringBuilder sb = new StringBuilder();
        int i = 0;
        int dir = 1;

        // 方向遍历，遇到括号就跳转并反向
        while (i >= 0 && i < n) {
            char ch = s.charAt(i);
            if (ch == '(' || ch == ')') {
                i = pair[i];
                dir = -dir;
            } else {
                sb.append(ch);
            }
            i += dir;
        }

        return sb.toString();
    }
}

func reverseParentheses(s string) string {
	n := len(s)
	pair := make([]int, n)
	stack := make([]int, 0)

	// 预处理每个括号的配对位置
	for i := 0; i < n; i++ {
		if s[i] == '(' {
			stack = append(stack, i)
		} else if s[i] == ')' {
			j := stack[len(stack)-1]
			stack = stack[:len(stack)-1]
			pair[i] = j
			pair[j] = i
		}
	}

	res := make([]byte, 0, n)
	i, dir := 0, 1

	// 方向遍历，遇到括号就跳转并反向
	for i >= 0 && i < n {
		if s[i] == '(' || s[i] == ')' {
			i = pair[i]
			dir = -dir
		} else {
			res = append(res, s[i])
		}
		i += dir
	}

	return string(res)
}

相似题目

题目	难度	考察点
20. 有效的括号	简单	栈
394. 字符串解码	中等	栈
1249. 移除无效的括号	中等	栈
856. 括号的分数	中等	栈
1614. 括号的最大嵌套深度	简单	栈

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/76749252