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

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

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

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reverse-substrings-between-each-pair-of-parentheses
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

栈

import java.util.Deque;
import java.util.LinkedList;

class Solution {
    public String reverseParentheses(String s) {
        Deque stack = new LinkedList();
        StringBuilder ans = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                stack.push(ans.toString());
                ans.setLength(0);
            } else if (s.charAt(i) == ')') {
                ans.reverse();
                ans.insert(0, stack.pop());
            } else {
                ans.append(s.charAt(i));
            }
        }
        return ans.toString();
    }
}

预处理

import java.util.Deque;
import java.util.LinkedList;
import java.util.Scanner;

class Solution {
    public String reverseParentheses(String s) {
        Deque stack = new LinkedList<>();
        int[] pairs = new int[s.length()];
        for (int i = 0; i < s.length(); ++i) {
            if (s.charAt(i) == '(') {
                stack.push(i);
            } else if (s.charAt(i) == ')') {
                int pop = stack.pop();
                pairs[pop] = i;
                pairs[i] = pop;
            }
        }
        StringBuilder ans = new StringBuilder();
        int index = 0, step = 1;
        while (index < s.length()) {
            if (s.charAt(index) == '(' || s.charAt(index) == ')') {
                step = -step;
                index = pairs[index];
            } else {
                ans.append(s.charAt(index));
            }
            index += step;
        }
        return ans.toString();
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            System.out.println(new Solution().reverseParentheses(in.next()));
        }
    }
}