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

力扣 LeetCode

1190. 反转每对括号间的子串 - 力扣（LeetCode）

1190. 反转每对括号间的子串 - 给出一个字符串 s（仅含有小写英文字母和括号）。

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

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

示例 1：

输入：s = "(abcd)"
输出："dcba"

示例 2：

输入：s = "(u(love)i)"
输出："iloveu"
解释：先反转子字符串 "love" ，然后反转整个字符串。

示例 3：

输入：s =...

思路

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