反转每对括号间的子串

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

题目说明

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

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

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

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

示例

示例 1：

1 2	输入：s = "(abcd)" 输出："dcba"

示例 2：

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

示例 3：

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

示例 4：

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

笔者理解

此题是一道字符串算法问题，在力扣题库中被定义为中等题。

解法

当笔者阅读完此题后，发现此题用栈求解比较合适，直接根据题目中的要求，每遇见一个括号的组合就进行翻转，让我们来看看具体如何实现的吧。

实现

public String reverseParentheses(String s) {
        StringBuilder sb = new StringBuilder();

        // 录入字符串
        Deque<Character> stack = new LinkedList();

        // 暂存括号内字符，并反序填充回去
        Deque<Character> temp = new LinkedList();

        for (int i = 0; i < s.length(); i++) {
            // 每遇到一个')'就操作一次
            if (s.charAt(i) == ')') {
                while (stack.getLast() != '(') {
                    temp.add(stack.removeLast());
                }
                // 去除原数组中的'('
                stack.removeLast();

                // 倒序填充回去
                while(!temp.isEmpty()) {
                    stack.add(temp.removeFirst());
                }
            }
            // 没遇到')'时不断录入字符
            else {
                stack.add(s.charAt(i));
            }
        }

        while(!stack.isEmpty()) {
            // 队尾填充字符，所以从队首取回字符
            sb.append(stack.removeFirst());
        }

        return sb.toString();
    }