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

# 题目

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

[https://leetcode-cn.com/problems/reverse-substrings-between-each-pair-of-parentheses/](https://leetcode-cn.com/problems/reverse-substrings-between-each-pair-of-parentheses/)

给出一个字符串 `s`（仅含有小写英文字母和括号）。

请你按照从括号内到外的顺序，逐层反转每对匹配括号中的字符串，并返回最终的结果。

注意，您的结果中 **不应** 包含任何括号。

**示例 1：**

```
输入：s = "(abcd)"
输出："dcba"
```

**示例 2：**

```
输入：s = "(u(love)i)"
输出："iloveu"
```

**示例 3：**

```
输入：s = "(ed(et(oc))el)"
输出："leetcode"
```

**示例 4：**

```
输入：s = "a(bcdefghijkl(mno)p)q"
输出："apmnolkjihgfedcbq"
```

**提示：**

- `0 <= s.length <= 2000`
- `s` 中只有小写英文字母和括号
- 我们确保所有括号都是成对出现的

# 题解

## 思路

利用栈，遇到括号对括号内的数据出栈，再入栈

## 代码

```javascript
/**
 * @param {string} s
 * @return {string}
 */
var reverseParentheses = function(s) {
    // 答案
    const ans = [];
    // 缓存
    let tmp = [];
    // 字符
    let str;
    for(let i = 0; i < s.length; i++){
        if(s[i] != ')') {
            ans.push(s[i]);
        } else {
            // 开始前清空
            tmp = [];
            // 弹出数据直到(
            do {
                str = ans.pop();
                tmp.push(str);
            } while(str !== '(');
            // 删除最后一个(
            tmp.pop();
            // 翻转后插入到栈
            tmp.forEach(a => ans.push(a));
        }
    }
    return ans.join('');
};
```

## 官方

#### 方法一：栈

**思路及算法**

本题要求按照从括号内到外的顺序进行处理。如字符串 `(u(love)i)`，首先处理内层括号，变为 `(uevoli)`，然后处理外层括号，变为 `iloveu`。

对于括号序列相关的题目，通用的解法是使用递归或栈。本题中我们将使用栈解决。

我们从左到右遍历该字符串，使用字符串 `str` 记录当前层所遍历到的小写英文字母。对于当前遍历的字符：

* 如果是左括号，将 `str` 插入到栈中，并将 `str` 置为空，进入下一层；
* 如果是右括号，则说明遍历完了当前层，需要将 `str` 反转，返回给上一层。具体地，将栈顶字符串弹出，然后将反转后的 `str` 拼接到栈顶字符串末尾，将结果赋值给 `str`。
* 如果是小写英文字母，将其加到 `str` 末尾。

注意到我们仅在遇到右括号时才进行字符串处理，这样可以保证我们是按照从括号内到外的顺序处理字符串。

**代码**

```javascript
var reverseParentheses = function(s) {
    const stk = [];
    let str = '';
    for (const ch of s) {
        if (ch === '(') {
            stk.push(str);
            str = '';
        } else if (ch === ')') {
            str = str.split("").reverse().join("");
            str = stk[stk.length - 1] + str;
            stk.pop();
        } else {
            str += ch;
        }
    }
    return str;
};
```

#### 方法二：预处理括号

**思路及算法**

我们可以将括号的反转理解为逆序地遍历括号，如下图：

![fig1](/media/202105/2021-05-27_000756.png)

1. 第一步我们向右移动到左括号，此时我们跳跃到该左括号对应的右括号（进入了更深一层）；
2. 第二到第三步我们在括号内部向左移动（完成了更深层的遍历）；
3. 第四步我们向左移动到左括号，此时我们跳跃到该左括号对应的右括号（返回到上一层）；
4. 第五步我们在括号外向右移动（继续遍历）。

读者们可以自行尝试模拟两层乃至多层括号嵌套的移动方案，规律可以从当前的单层括号中总结出来。

假设我们沿着某个方向移动，此时遇到了括号，那么我们只需要首先跳跃到该括号对应的另一个括号所在处，然后改变我们的移动方向即可。这个方案同时适用于遍历时进入更深一层，以及完成当前层的遍历后返回到上一层的方案。

在实际代码中，我们需要预处理出每一个括号对应的另一个括号所在的位置，这一部分我们可以使用栈解决。当我们预处理完成后，即可在线性时间内完成遍历，遍历的字符串顺序即为反转后的字符串。

**代码**

```javascript
var reverseParentheses = function(s) {
    const n = s.length;
    const pair = new Array(n).fill(0);
    const stack = [];
    for (let i = 0; i < n; i++) {
        if (s[i] === '(') {
            stack.push(i);
        } else if (s[i] == ')') {
            const j = stack.pop();
            pair[i] = j;
            pair[j] = i;
        }
    }