1190. 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)。具体实现见下面代码。

代码

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)
}