394.字符串解码

递归实现

这里递归的时候i是引用，目的是为了避免多个[]嵌套的时候，定位完成后函数该继续的位置。

class Solution {
public:
    string decodeString(string s) {
        int i = 0;
        return dfs(s, i);
    }
    string dfs(string& s, int& i)
    {
        if(i >= s.size())
            return "";
        string ns;
        if(s[i] == ']')
            return ns;
        else if(s[i] <= '9' && s[i] > '0'){
            int cot = 0, ti = i;
            while(s[i] != '[') {
                ++i; 
                ++cot;
            }    
            string nus = s.substr(ti, cot);
            int k = atoi(nus.c_str());
            string ts = dfs(s, ++i);
            for(int j = 0; j < k; ++j)
                ns += ts;
            
            ns += dfs(s, ++i);
        } else {
            ns += s[i];
            ns +=  dfs(s, ++i);
        }
        return ns;
    }
};

Accepted

29/29 cases passed (0 ms)

Your runtime beats 100 % of cpp submissions

Your memory usage beats 11.06 % of cpp submissions (9.1 MB)

非递归实现

class Solution {
public:
    string decodeString(string s) {
        stack<pair<int, string>> stk;
        int multi = 0;
        string pre = "";
        for(auto c : s) {
            if(c >= '0' && c <= '9') {
                if(!multi)
                    multi = c - 48;
                else {
                    multi *= 10;
                    multi += c - 48;
                }
            }
            else if (c == '[') {
                stk.push({multi, pre});
                multi = 0;
                pre = "";
            }
            else if (c == ']') {
                auto p = stk.top();
                stk.pop();
                string tm = pre;
                pre = p.second;
                for(int i = 0; i < p.first; ++i)
                    pre += tm;
            } else {
                pre += c;
            }
        }
        return pre;
    }
};