flag

软件学院大三党，每天一道算法题，第23天

题目介绍

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

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

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

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/reverse-substrings-between-each-pair-of-parentheses

思路

采用一个栈，当遇到左括号时将左括号入栈，当遇到右括号的时候,将栈顶的左括号弹出，同时将两括号之间的内容全部反转。

关键代码

public static String reverseParentheses(String s) { StringBuilder stringBuilder=new StringBuilder(); char[]arr=s.toCharArray(); Stack<Integer>stack=new Stack<>();//存字符index的栈 for(int i=0;i<arr.length;i++){ if(arr[i]=='(') stack.push(i); if(arr[i]==')') reverse(arr,stack.pop()+1,i-1);//括号之间的内容进行颠倒 } for(int i=0;i<arr.length;i++){ if(arr[i]!='('&&arr[i]!=')') stringBuilder.append(arr[i]); } return stringBuilder.toString(); } public static void reverse(char[] arr, int left, int right) {//将数组所有元素颠倒 while (right > left) { char tmp = arr[left]; arr[left] = arr[right]; arr[right] = tmp; right--; left++; } }

参考资料