问题

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

思路

好久没写题，一个暴力想了半天，类似反转之类的首先想到的就是栈，暴力的思路就是：

• 碰到 ( 或字符：入栈
• 碰到 )或字符：弹栈，直到碰到最临近的栈内的 （ 结束，将拿到的串，顺序再次入栈。这种操作相当于「子字符串反转」并「更新到原串」的效果

import java.util.*;

class Solution {
    public String reverseParentheses(String s) {
        int p = 0;
        int len = s.length();
        if (len == 0) {
            return s;
        }
        Deque<Character> stack = new ArrayDeque<>(len);
        StringBuilder ss = new StringBuilder(len);
        while (p < len) {
            Character c = s.charAt(p);
            if (!c.equals(')')) {
                // pop
                stack.push(c);
            } else {
                // pop and push again
                reverseAndPush(stack);
            }
            p++;
        }
        while (!stack.isEmpty()) {
            ss.append(stack.pop());
        }
        return ss.reverse().toString();
    }

    private void reverseAndPush(Deque<Character> stack) {
        List<Character> list = new ArrayList<>(stack.size());
        while (true) {
            Character c = stack.pop();
            if (c.equals('(')) {
                break;
            }
            list.add(c);
        }
        list.forEach(stack::push);
    }
}

总结

好久没写题，集成插件到 IDE 写，近期有空的话偶尔先恢复一下状态吧...

写这道题的收获是之前一直使用 Stack，今天 SonarLint 提示没必要用，因为它的挺多的压栈弹栈都用重量锁了，于是就换成 Deque 了