题目地址
个人博客地址
题目描述
给出一个字符串 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;}}