2021/5/26 反转每对括号间的子串

题目描述

描述转载自力扣《1190. 反转每对括号间的子串》

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

解题思路

1. 从字符串中从里到外逐个找到匹配的一对括号，将括号里的字符串反转，这就要求我们记录左括号和右括号的位置；
2. 寻找匹配的括号，可以使用栈存储，遇到 "(" ，存储左括号所在的索引，遇到 ")"，将栈顶的左括号的索引取出，至此，我们就能获得匹配的左括号和右括号的索引。因为题目确保所有括号是成对出现的，所以无需过多处理；
3. 根据这对括号的索引，将括号内的字符进行反转。

Java代码实现

class Solution {
    public String reverseParentheses(String s) {
        Stack<Integer> stack = new Stack<>();
        char[] cSeq = s.toCharArray();
        for (int i = 0; i < s.length(); ++i) {
            if (s.charAt(i) == '(') {
                stack.push(i);
            } else if (s.charAt(i) == ')') {
                int left = stack.pop();
                reverse(cSeq, left, i);
            }
        }

        StringBuilder sb = new StringBuilder();
        for (char c : cSeq) {
            if (c != ' ') {
                sb.append(c);
            }
        }
        return sb.toString();
    }

    public void reverse(char[] cSeq, int left, int right) {
        cSeq[left] = cSeq[right] = ' ';
        int mid = (right - left + 1) >> 1;
        for (int i = 1; i < mid; ++i) {
            char temp = cSeq[left + i];
            cSeq[left + i] = cSeq[right - i];
            cSeq[right - i] = temp;
        }
    }
}