# [1190. Reverse Substrings Between Each Pair of Parentheses](https://leetcode.com/problems/reverse-substrings-between-each-pair-of-parentheses/)


## 题目

You are given a string `s` that consists of lower case English letters and brackets.

Reverse the strings in each pair of matching parentheses, starting from the innermost one.

Your result should **not** contain any brackets.

**Example 1:**

```
Input: s = "(abcd)"
Output: "dcba"
```

**Example 2:**

```
Input: s = "(u(love)i)"
Output: "iloveu"
Explanation: The substring "love" is reversed first, then the whole string is reversed.
```

**Example 3:**

```
Input: s = "(ed(et(oc))el)"
Output: "leetcode"
Explanation: First, we reverse the substring "oc", then "etco", and finally, the whole string.
```

**Example 4:**

```
Input: s = "a(bcdefghijkl(mno)p)q"
Output: "apmnolkjihgfedcbq"
```

**Constraints:**

- `0 <= s.length <= 2000`
- `s` only contains lower case English characters and parentheses.
- It's guaranteed that all parentheses are balanced.

## 题目大意

给出一个字符串 s（仅含有小写英文字母和括号）。请你按照从括号内到外的顺序，逐层反转每对匹配括号中的字符串，并返回最终的结果。注意，您的结果中 不应 包含任何括号。

## 解题思路

- 本题最容易想到的思路是利用栈将每对括号里面的字符串入栈，当遇到 ")" 括号时出栈并逆序。由于用到了栈的数据结构，多层括号嵌套的问题也不用担心。这种边入栈出栈，逆序字符串的方法，时间复杂度是 O(n^2)，有没有可能进一步降低时间复杂度呢？
- 上述解法中，存在重复遍历的情况。扫描原字符串的时候，入栈出栈已经扫描了一次，在 ")" 括号出栈时，逆序又会扫一遍已经入栈的字符串。这部分重复遍历的过程可以优化掉。第一次循环先标记出逆序区间。例如遇到 "(" 的时候，入栈并记录下它的下标，当遇到 ")" 的时候，意味着这一对括号匹配上了，所以将 ")" 的下标和之前入栈 "(" 的下标交换。此次遍历将逆序区间标记出来了。再遍历一次，根据逆序区间逆序字符串。不在逆序区间的字符串正常 append。如果在逆序区间内的，逆序遍历，添加到最终结果字符串中。这样做，时间复杂度仅为 O(n)。具体实现见下面代码。

## 代码

```go
package leetcode

func reverseParentheses(s string) string {
	pair, stack := make([]int, len(s)), []int{}
	for i, b := range s {
		if b == '(' {
			stack = append(stack, i)
		} else if b == ')' {
			j := stack[len(stack)-1]
			stack = stack[:len(stack)-1]
			pair[i], pair[j] = j, i
		}
	}
	res := []byte{}
	for i, step := 0, 1; i < len(s); i += step {
		if s[i] == '(' || s[i] == ')' {
			i = pair[i]
			step = -step
		} else {
			res = append(res, s[i])
		}
	}
	return string(res)
}
```