mirror of
https://github.com/halfrost/LeetCode-Go.git
synced 2025-07-07 18:10:29 +08:00
84 lines
2.8 KiB
Markdown
84 lines
2.8 KiB
Markdown
# [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)
|
||
}
|
||
``` |