好题记录 Leetcode 394.字符串解码中等难度

在这里插入图片描述

方法一：递归

思路很简单，比较好理解，注意细节处理！！！

class Solution {
public:string decodeString(string s) {string ans;for(int i=0;s[i]!=0;i++){if(s[i]>='a'&&s[i]<='z')ans+=s[i];if(s[i]>='0'&&s[i]<='9'){int times=0;while(s[i]>='0'&&s[i]<='9'){times=times*10+s[i]-'0';i++;} //结束时i的位置是'['int pos=i+1;//i+1为这组[]内的第一个元素int flag=1;  //存在某个[没有配对的时候 flag为1，每一对左右括号都配对后flag=0while(flag){i++;if(s[i]=='[')   flag++;if(s[i]==']')   flag--;}//这个循环结束时i的位置是配对结束时']'的位置string tmp=decodeString(s.substr(pos,i-pos));for(int j=0;j<times;j++)ans+=tmp;}}return ans;}
};

方法二：数字栈与字符串栈

在这里插入图片描述

class Solution {
public:string decodeString(string s) {string res="";stack<int> nums;stack<string> strs;int times=0;  //记录次数for(int i=0;i<s.size();i++){if(s[i]>='a'&&s[i]<='z')  //a-z直接加入res后res+=s[i];else if(s[i]>='0'&&s[i]<='9'){  //碰到0-9化成次数，数字可能连续好几位要注意times=times*10+s[i]-'0'; }else if(s[i]=='['){      //碰到左括号[,将当前res和当前times各自入栈，并分别置空和置0nums.push(times);strs.push(res);times=0;res="";}else {   //碰到右括号]时，操作如下int tmp=nums.top();  //数字栈的栈顶元素表示次数tmp，然后出栈nums.pop();    while(tmp--)  strs.top()+=res; //将当前res添加tmp次到字符串栈的栈顶后，再赋给res后出栈res=strs.top();    //之后若还是字母，就会直接加到res之后，因为它们是同一级的运算//若是左括号，res会被压入strs栈，作为上一层的运算strs.pop();}}return res;}
};