题目链接：1190. 反转每对括号间的子串（中等）
算法原理：
解法一：栈
时间复杂度O(N²)
2ms击败65.24%
我们用 StringBuilder 记录当前括号内部字符
①遇到 (：将当前 StringBuilder 内容压入栈，清空它，准备记录新的括号内部字符
②遇到 )：反转当前 StringBuilder（括号内子串），弹出栈顶的外层字符串，拼到反转内容前面
③普通字符：直接追加到 StringBuilder
遍历完成，StringBuilder 即为结果
答疑：insert 那部分没懂~~
sb.insert(0,stack.pop());把弹出来的外层字符串，插到当前 sb 的最开头
拿示例一 (u(love)i) 拆解：
当内层 (love) 碰到右括号 )
1.当前 sb="love"（括号里面收集到的字符）
2.执行 sb.reverse()→sb 变成 "evol"
3.stack.pop() 拿到栈顶："u"
4.sb.insert(0,"u")：在索引0 最前面插入 "u"
sb 从 evol 变成 uevol
接下来拆解 (u(love)i) 最后面的 )
此时 sb 为 uevoli
1.sb.reverse()→iloveu
2.栈pop拿到""（因为最外层左括号前面是空字符串）
3.insert(0,"") ，空串插开头不变，sb 保持 iloveu 就是答案
解法二：递归
时间复杂度O(N²)
1ms击败97.43%
递归过程中，用一个在递归方法外的变量 i 表示当前下标，每遍历到一个字符，就把 i 加一
在递归方法 f 内部新建 StringBuilder ret，收集当前层级的字符
①遇到 (：开启内层括号，递归调用 f()，拿到内层处理并反转完成的字符串，追加到当前 ret（递归的“递”）
②遇到 )：当前这一对括号内的字符收集完毕，反转 ret，把反转后的串返回给上一层（递归的“归”）
③普通字符：直接追加到 ret
遍历完成，ret 即为结果
Java代码：
class Solution { //1190. 反转每对括号间的子串 //解法一：栈 public String reverseParentheses(String s) { Deque<String> stack=new LinkedList<>(); StringBuilder sb=new StringBuilder(); for(char c:s.toCharArray()){ if(c=='('){ //左括号：把当前暂存字符串压栈，清空sb准备存括号内的内容 stack.push(sb.toString()); sb.setLength(0); }else if(c==')'){ //右括号：反转当前括号内字符串，和栈顶拼接 sb.reverse(); sb.insert(0,stack.pop()); }else{ //普通字母，直接追加 sb.append(c); } } return sb.toString(); } }class Solution { //1190. 反转每对括号间的子串 //解法二：递归 private int i=0; public String reverseParentheses(String S) { char[] s=S.toCharArray(); return f(s).toString(); } private StringBuilder f(char[] s){ StringBuilder ret=new StringBuilder(); while(i<s.length){ char ch=s[i]; i++; //归 if(ch==')') return ret.reverse(); //递 if(ch=='(') ret.append(f(s)); //字母 else ret.append(ch); } return ret; } }
