每日题解:LeetCode 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 中只有小写英文字母和括号
我们确保所有括号都是成对出现的
解法
class Solution {
public String reverseParentheses(String s) {
Stack<Integer> stack = new Stack<>();
char[] temp = s.toCharArray();
int len = s.length();
for (int i = 0; i < len; i++) {
if (temp[i] == '(') {
stack.push(i);
} else if (temp[i] == ')') {
reverse(temp, stack.pop()+1, i-1);
}
}
StringBuilder stringbuilder=new StringBuilder();
for (char c : temp) {
if (c != '('&& c != ')') {
stringbuilder.append(c);
}
}
return stringbuilder.toString();
}
public void reverse(char[] arr, int left, int right) {
while (left<right) {
char temp=arr[left];
arr[left]=arr[right];
arr[right]=temp;
++left;
--right;
}
}
}
解题思路
栈
以(ed(et(oc))el)"为例子，按照题目的意思
1、 反转最里面的(oc)的字符，得到字符(ed(etco)el)
2、 然后反转ed(etco)外边的字符(edocteel)
3、 最后反转整个字符leetcode
栈顶元素记录(的下标，当遇到)，反转()内的字符
for (int i = 0; i < len; i++) {
//记录下标
if (temp[i] == '(') {
stack.push(i);
} else if (temp[i] == ')') {
//反转字段
reverse(temp, stack.pop()+1, i-1);
}
}
反转字符的方法
public void reverse(char[] arr, int left, int right) {
while (left<right) {
char temp=arr[left];
arr[left]=arr[right];
arr[right]=temp;
++left;
--right;
}
}