README.md

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

English Version

题目描述

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

解法

用双端队列或者栈，模拟反转过程

Python3

class Solution:
    def reverseParentheses(self, s: str) -> str:
        stack = []
        for c in s:
            if c == ")":
                tmp = []
                while stack[-1] != "(":
                    tmp += stack.pop()
                stack.pop()
                stack += tmp
            else:
                stack.append(c)
        return "".join(stack)

Java

class Solution {
    public String reverseParentheses(String s) {
        Deque<Character> deque = new ArrayDeque<>();
        for (char c : s.toCharArray()) {
            if (c == ')') {
                StringBuilder sb = new StringBuilder();
                while (deque.peekLast() != '(') {
                    sb.append(deque.pollLast());
                }
                deque.pollLast();
                for (int i = 0, n = sb.length(); i < n; i++) {
                    deque.offerLast(sb.charAt(i));
                }
            } else {
                deque.offerLast(c);
            }
        }
        StringBuilder sb = new StringBuilder();
        while (!deque.isEmpty()) {
            sb.append(deque.pollFirst());
        }
        return sb.toString();
    }
}

JavaScript

/**
 * @param {string} s
 * @return {string}
 */
var reverseParentheses = function(s) {
    let stack = [];
    let hashMap = {};
    const n = s.length;
    for (let i = 0; i < n; i++) {
        let cur = s.charAt(i);
        if (cur == '(') {
            stack.push(i);
        } else if (cur == ')') {
            let left = stack.pop();
            hashMap[left] = i;
            hashMap[i] = left;
        }
    }
    let res = [];
    let i = 0;
    let step = 1; // 1向右，-1向左
    while (i > -1 && i < n) {
        let cur = s.charAt(i);
        if (cur == '(' || cur == ')') {
            step = -step;
            i = hashMap[i];
        } else {
            res.push(cur);
        }
        i += step;
    }
    return res.join('');
};

...