题目大意：
反转每对括号间的子串
给出一个字符串 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 <= 2000s中只有小写英文字母和括号- 我们确保所有括号都是成对出现的
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1190
解题思路分析：
原字符串包含多层括号嵌套，翻转顺序由内至外，很容易想到使用递归思路来解题。当我们看到正括号时，说明需要进入下一层的嵌套，这时将问题扔给递归子问题去解决。当遇到反括号时，说明本层嵌套结束，此时应该结束当前递归返回递归函数上一层。如果遇到的是小写字母，我们就将其按顺序拼接起来，在本层递归结束时反转后返回给上一层即可。因此每一层的递归函数大概是下面这样：
String helper(){
String result = "小写字母" + "(" + "递归函数返回结果helper()" +")" + "小写字母";
result.reverse();
return result;
}当递归结束时，所有的字符都会按条件反转，注意的是，最外层如果没有括号，那么最外层是不需要反转的。另外，这个结果中包含括号字符，应该在最后将其全部删除。
看下实现代码：
public String reverseParentheses(String s) {
// 先递归反转所有字符
String temp= helper(s, 0, 0).toString();
// 删除所有括号字符
StringBuilder sb = new StringBuilder();
for(int i=0;i<temp.length();i++){
if(temp.charAt(i)!=')' && temp.charAt(i)!='('){
sb.append(temp.charAt(i));
}
}
return sb.toString();
}
// 递归函数
// s为原字符串
// index为字符当前的下标
// level为括号嵌套深度，默认0为最外层无括号
public StringBuilder helper(String s, int index, int level){
StringBuilder sb = new StringBuilder(); // 返回结果
for(int i=index;i<s.length();i++){ // 从index开始遍历字符串
char c = s.charAt(i); // 当前字符
if(c == '('){ // 如果为正括号，说明出现嵌套
// 递归得到嵌套括号内的反转字符串
StringBuilder child = helper(s, i+1, level+1);
// 返回值加上正括号以及嵌套括号内的反转字符串
sb.append("(").append(child);
// 嵌套内容已经遍历过，因此当前下标跳到嵌套子字符串之后
i+=(child.length());
}else if(c == ')'){ // 如果为反括号，说明嵌套结束
// 如果为最外层，没有上层可以返回，需要继续向后循环到结束
if(level==0){
continue;
}
// 返回结果加上反括号后，反转并返回给上层递归
return sb.append(")").reverse();
}else{
// 小写字母直接加到返回值中
sb.append(c);
}
}
return sb;
}本解法运行时间为1ms。
Runtime: 1 ms, faster than 98.09% of Java online submissions for Reverse Substrings Between Each Pair of Parentheses.
Memory Usage: 34.8 MB, less than 100.00% of Java online submissions for Reverse Substrings Between Each Pair of Parentheses.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-1190-reverse-substrings-between-each-pair-of-parentheses-解题思路分析/