Leetcode每日一题 —— 1190. 反转每对括号间的子串

思路

一开始想着不用递归和字符串，借助括号的首尾记录和字符数组来构造字符串，但是发现反倒是更复杂了。最终还是回归简单，按深度直接DFS。

遇到’(‘直接交给下一层DFS，返回的时候位置跳到下一层后面，直到遇到当前层’)'为止。

代码

class Solution {

    private char[] chars;

    public String reverseParentheses(String s) {

        chars = s.toCharArray();

        Pair<Integer, StringBuilder> pair = dfs(0);

        return pair.getValue().toString();

    }

    private Pair<Integer, StringBuilder> dfs(int idx) {

        StringBuilder ans = new StringBuilder();

        while (idx < chars.length && chars[idx] != ')') {

            if (chars[idx] == '(') {

                Pair<Integer, StringBuilder> pair = dfs(idx + 1);

                idx = pair.getKey();

                ans.append(pair.getValue().reverse());

            } else {

                ans.append(chars[idx]);

            }

            idx++;

        }

        return new Pair<>(idx, ans);

    }

}