宁波网站设计企业,手机视频制作软件最火,wordpress 防调用,电视直播网站建设给出一个字符串 s#xff08;仅含有小写英文字母和括号#xff09;。
请你按照从括号内到外的顺序#xff0c;逐层反转每对匹配括号中的字符串#xff0c;并返回最终的结果。
注意#xff0c;您的结果中 不应 包含任何括号。
示例 1#xff1a; 输入#xff1a;s “…给出一个字符串 s仅含有小写英文字母和括号。
请你按照从括号内到外的顺序逐层反转每对匹配括号中的字符串并返回最终的结果。
注意您的结果中 不应 包含任何括号。
示例 1 输入s “(abcd)” 输出“dcba”
示例 2 输入s “(u(love)i)” 输出“iloveu” 解释先反转子字符串 “love” 然后反转整个字符串。
示例 3 输入s “(ed(et(oc))el)” 输出“leetcode” 解释先反转子字符串 “oc” 接着反转 “etco” 然后反转整个字符串。
提示 1 s.length 2000 s 中只有小写英文字母和括号 题目测试用例确保所有括号都是成对出现的
栈
class Solution {
public:string reverseParentheses(string s) {stackstring st;string str;for(char c : s){if(c (){st.push(str);str ;}else if(c )){reverse(str.begin(), str.end());str st.top() str;st.pop();}else{str.push_back(c);}}return str;}
};时间复杂度O(n ^ 2 )其中 n 为字符串的长度。栈的最大深度为 O(n)每一层处理的时间复杂度主要为反转的时间复杂度为 O(n)因此总时间复杂度为 O(n ^ 2 )。 空间复杂度O(n)其中 n 为字符串的长度。对于任意时刻字符串中的任意一个字符至多只被栈中的一个位置包含一次。
使用栈的方法具体思路就是我们定义一个字符串每当遍历到一个字母我们就push到字符串str中当遇到一个左括号我们就将这个字符串push到栈中存着令字符串重新为空。当遇到一个右括号的时候我们令这个右括号对应的左括号之间的字符串进行反转这时候我们栈的顶部存放着外面一层左括号到当前右括号对应左括号之间的字符串我们令字符串为str st.top() str;然后遇到新的字母继续加入到str中。遇到右括号就让这个str继续反转这样子就完成了从内层括号到外层括号之间字符串不断反转的过程。 预处理括号
class Solution {
public:string reverseParentheses(string s) {int n s.length();vectorint pair(n);stackint stk;for (int i 0; i n; i) {if (s[i] () {stk.push(i);} else if (s[i] )) {int j stk.top();stk.pop();pair[i] j, pair[j] i;}}string ret;int index 0, step 1;while (index n) {if (s[index] ( || s[index] )) {index pair[index];step -step;} else {ret.push_back(s[index]);}index step;}return ret;}
};时间复杂度O(n)其中 n 为字符串的长度。预处理出括号的对应关系的序列的时间复杂度为 O(n)遍历字符串的时间复杂度同样为 O(n)。
空间复杂度O(n)其中 n 为字符串的长度。栈的大小不会超过 n以及我们需要 O(n) 的空间记录括号的对应关系。
我们先定义一个pair他用来储存每个括号对应的另一半括号的位置。 这个解法的关键点就是他不使用先查找再反转的方式而直接输出了反转后的内容。这个办法的核心思想是 举例子s “(u(love)i)” 我们能知道在最外层括号是翻转一次而最内层括号是翻转后又反转的内容所以最内层括号在加入到ret的时候是love。
让我们来模拟当遍历s到第一个左括号的时候他根据pair记录查找到最外层有括号位置然后遍历方向改变成向左这时候遇到iret “i”然后遍历到内层有括号索引转换到最内层左括号方向向右这时候一一推入’l’,‘o’,‘v’,‘e’此时ret “ilove”然后遇到内层有括号他根据pair将索引转换到内层左括号方向向左然后加入元素’u’此时ret就是iloveu。然后遍历到外层左括号索引转换到右括号然后index再加上向右方向的step此时index不再小于n那么不会进入while循环。最后结果就是ret “iloveu”。
