394 字符串解码

下面是题目

下面是题目给出的模板

class Solution {
public:
    string decodeString(string& s) {
    }
};

题解

1. 这题不看题解我真滴很难做，思路是有一点，但是要把它编程代码其实不简单！贴一下大佬的代码

class Solution {
public:
    typedef pair<int,string> pis;
    //将字符串str重复times次
    string repeat(const string& str, int times) {
        string retString = "";
        for(int i = 0; i < times; ++i) retString += str;
        return retString;
    }
    //先思考：栈应存储什么元素，何时进栈、出栈
    string decodeString(string& s) {
        int repeatTims = 0;
        string res = "";
        vector<pis> vecStack;   //用vector代替stack，更高效，因为stack底层可以是vector
        for(auto i : s) {
            //计算字符串需要重复的次数
            if('0'<=i && i<='9') repeatTims = (repeatTims*10)+(i-'0');  
            //如果遇到[的话，我们要把现有的res和需要重复[]中元素的次数 入栈，res可以为""
            else if(i == '[') {
                vecStack.push_back({repeatTims,res});
//进栈后要更新res和repeatTimes，并不担心最后返回的res为空，因为之前更新的res在遇到'['又会被进栈
                //不懂这问题的可以手动模拟一下这个样例：3[a]2[bc]ef
                //实现下一层遍历之前，要初始化res和repeatTimes
                res = "";
                repeatTims = 0;
            }
            //如果是]的话，这时候的res就是[]中的字符串了，我们要把他重复
            else if(i == ']') {
                //把相当于取top()
                pis tmp = vecStack[vecStack.size()-1];
                vecStack.pop_back();
                res = tmp.second + (tmp.first==0 ? "" : repeat(res, tmp.first));a
            }
            else res += i;
        }
        return res;
    }
};

/*我们拿s = "3[a2[c]]"手动模拟一遍
拿到3，repeattime = 3
拿到[,把(3,"")入栈，res="",repeattime = 0
拿到a，res=a
拿到2，repeattime=2
拿到[,把(2,a)入栈，res="",repeattime = 0
拿到c.res=c
拿到],res=a+repeat(c,2)=acc
拿到],res=""+repeat(acc,3)=accaccacc
结束

再拿2[abc]3[cd]ef举例子
拿到2，repreattime = 2
拿到[,把(2,"")入栈，res="",repeattime = 0;
拿到a,res=a
拿到b，res=ab
拿到c，res=abc
拿到],把(2,"")出栈，res=""+repeat(2,"abc")=abcabc
拿到3，repeattime = 3
拿到[，把(3,"abcabc")入栈，res="",repeattime = 0;
拿到c，res= c;
拿到d，res=cd;
拿到],把(3,"abcabc")出栈，res=abcabc+repeat(3,cd)=abcabccdcdcd
拿到e，res=abcabccdcdcde
拿到f，res=abcabccdcdcdef
*/

利用栈解法

//利用辅助栈的解法，同样用两个例子分析
string decodeString(string s) {
    stack<int> numStack;
    stack<string> resStack;
    int num = 0;
    string res;
    for (int i = 0; i < s.size(); i++) {
        if (isalpha(s[i])) {
            res.push_back(s[i]);
        } else if (isdigit(s[i])) {
            num = num * 10 + s[i] - '0';
        } else if (s[i] == '[') {
            resStack.push(res);
            res = "";
            numStack.push(num);
            num = 0;
        } else {
            for (int j = 0; j < numStack.top(); j++) {
                resStack.top() += res;
            }
            numStack.pop();
            res = resStack.top();
            resStack.pop();
        }
    }
    return res;
}

/*
我们拿s = "3[a2[c]]"手动模拟一遍
拿到3，发现是数字，于是num=3
拿到[，resStack.push(""),numstack.push(3),num=0;
拿到a，是字符，那么res=a
拿到2，是数字，那么sum=2
拿到[,resStack.push("a"),numstack.push(2),num=0,res=""
拿到c，res=c
拿到],resStack.top()=a+2*c=acc ,res=resStack.top()=acc,resStack.pop()
拿到],resStack.top()=""+3*acc=accaccacc,res=resStack.top()=acc,resStack.pop()
最后，return res
*/

综上，我们可以看到其实这两种方法的本质都是相似的，只是一个利用pair存储，一个用两个栈分别存储数字和字符串