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

阅读量7次

题目

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

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 中只有小写英文字母和括号
我们确保所有括号都是成对出现的

题解

思路

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

代码


/**
 * @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 末尾。

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

代码


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

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

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

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

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

代码


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

    const sb = [];
    let index = 0, step = 1;
    while (index < n) {
        if (s[index] === '(' || s[index] === ')') {
            index = pair[index];
            step = -step;
        } else {
            sb.push(s[index]);
        }
        index += step;
    }
    return sb.join('');
};