题目链接1190. 反转每对括号间的子串中等算法原理解法一栈时间复杂度O(N²)2ms击败65.24%我们用 StringBuilder 记录当前括号内部字符①遇到 (将当前 StringBuilder 内容压入栈清空它准备记录新的括号内部字符②遇到 )反转当前 StringBuilder括号内子串弹出栈顶的外层字符串拼到反转内容前面③普通字符直接追加到 StringBuilder遍历完成StringBuilder 即为结果答疑insert 那部分没懂~~sb.insert(0,stack.pop());把弹出来的外层字符串插到当前 sb 的最开头拿示例一 (u(love)i) 拆解当内层 (love) 碰到右括号 )1.当前 sblove括号里面收集到的字符2.执行 sb.reverse()→sb 变成 evol3.stack.pop() 拿到栈顶u4.sb.insert(0,u)在索引0 最前面插入 usb 从 evol 变成 uevol接下来拆解 (u(love)i) 最后面的 )此时 sb 为 uevoli1.sb.reverse()→iloveu2.栈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) { DequeString stacknew LinkedList(); StringBuilder sbnew 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 i0; public String reverseParentheses(String S) { char[] sS.toCharArray(); return f(s).toString(); } private StringBuilder f(char[] s){ StringBuilder retnew StringBuilder(); while(is.length){ char chs[i]; i; //归 if(ch)) return ret.reverse(); //递 if(ch() ret.append(f(s)); //字母 else ret.append(ch); } return ret; } }
)
