题目描述

描述转载自力扣《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;
        }
    }
}