工装网站建设方案,广告传媒公司介绍,为什么做腾讯网站,苏州做网站价格Every day a Leetcode
题目来源#xff1a;394. 字符串解码
解法1#xff1a;栈
本题中可能出现括号嵌套的情况#xff0c;比如 2[a2[bc]]#xff0c;这种情况下我们可以先转化成 2[abcbc]#xff0c;在转化成 abcbcabcbc。我们可以把字母、数字和括号看成是独立的 TO…Every day a Leetcode
题目来源394. 字符串解码
解法1栈
本题中可能出现括号嵌套的情况比如 2[a2[bc]]这种情况下我们可以先转化成 2[abcbc]在转化成 abcbcabcbc。我们可以把字母、数字和括号看成是独立的 TOKEN并用栈来维护这些 TOKEN。
具体的做法是初始化一个栈 stk stackstring遍历字符串 s设当前字符为 cur s[i]
如果 cur 是一个数字字符设置一个字符串 num从当前下标 i 开始一直遍历下去直到 i 不是数字字符不断加入 num 中。最后将 num 压入栈中。如果 cur 是一个英文字母将该字符转换成字符串后压入栈中。如果 cur 是 ‘[’将该字符转换成字符串后压入栈中。否则cur 是 ‘]’新建一个字符串数组 sub不断将栈顶元素弹出直到栈顶元素是 “[”并插入到 sub 数组里。此时栈顶元素是 “[”这个没有用弹出然后新的栈顶就是一个数字字符串 num转为 int这个就是要重复的次数记为 repeatTime再将栈顶弹出。由于栈的特性数组 sub 中字符的顺序是倒置的我们先 reverse(sub.begin(), sub.end())再用字符串 temp 将 sub 中的字符串累加起来最后将 temp 重复 repeatTime 次最终得到的字符串压入栈顶。
最后将栈中的所有字符串累加起来再次由于栈的特性逆序才是正确答案。我们也可以用 insert 来将栈顶字符串插入到答案的开头来做
string ans ;
while (!stk.empty())
{ans.insert(0, stk.top())stk.pop();
}
return ans;代码
/** lc appleetcode.cn id394 langcpp** [394] 字符串解码*/// lc codestart
class Solution
{
public:string decodeString(string s){int n s.size(), i 0;stackstring stk;while (i n){char cur s[i];if (isdigit(cur)){string num ;while (isdigit(s[i])){num.push_back(s[i]);i;}stk.push(num);}else if (isalpha(cur) || cur [){stk.push(string(1, s[i]));i;}else // cur ]{vectorstring sub;while (stk.top() ! [){sub.push_back(stk.top());stk.pop();}reverse(sub.begin(), sub.end());stk.pop(); // 左括号出栈// 此时栈顶为当前 sub 对应的字符串应该出现的次数int repeatTime stoi(stk.top());stk.pop();string temp ;while (repeatTime--){for (string str : sub)temp str;}stk.push(temp);i;}}string ans ;while (!stk.empty()){ans.insert(0, stk.top());stk.pop();}return ans;}
};
// lc codeend结果 复杂度分析
时间复杂度O(S)其中 S 是解码后得出的字符串长度。除了遍历一次原字符串 s我们还需要将解码后的字符串中的每个字符都入栈并最终拼接进答案中故渐进时间复杂度为 O(S∣s∣)即 O(S)。
空间复杂度O(S)其中 S 是解码后得出的字符串长度。这里用栈维护 TOKEN栈的总大小最终与 S 相同。
