广宗网站建设,网站开发最新书籍,晋中建设集团网站,网站建设与维护教程题目
给出一个字符串 s#xff08;仅含有小写英文字母和括号#xff09;。
请你按照从括号内到外的顺序#xff0c;逐层反转每对匹配括号中的字符串#xff0c;并返回最终的结果。
注意#xff0c;您的结果中 不应 包含任何括号。 示例 1#xff1a;
输入#xff1a…题目
给出一个字符串 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”
解题思路
使用两个链表stack栈temp队列
只有需要翻转括号中的内容时才会把需要翻转的内容临时存在temp当中翻转之后则存在stack中stack里面只存有’(‘和字母当遇到’)‘时就说明存在一个完整的括号括号里面的内容需要翻转因此我们将stack的元素不断出栈并放入temp中存储直到遇到’(’说明当前括号内的内容已经全部出栈完毕了利用stack后进先出的特性所以将temp设置为先进先出的队列将stack的元素添加到temp的队尾再从temp的队头取元素即可达到翻转的效果
代码 public String reverseParentheses(String s) {LinkedListCharacter stack new LinkedList();LinkedListCharacter temp new LinkedList();for (int i 0; i s.length(); i) {if(s.charAt(i))){while (stack.getLast()!()temp.addLast(stack.removeLast());stack.removeLast();while (temp.size()0)stack.addLast(temp.removeFirst());}else {stack.addLast(s.charAt(i));}}StringBuilder res new StringBuilder();while (stack.size()0)res.append(stack.removeFirst());return res.toString();}
