394. Decode String

O(n) stack

class Solution {
public:
    string decodeString(const string &s) {
        stack<int> nums;
        string res;
        for (int i = 0; i < s.length(); ++i) {
            if (isdigit(s[i])) { // 遇到数字直接把整个数拼出来
                int x = 0, j = i;
                for (; j < s.length() && isdigit(s[j]); ++j) {
                    x = x * 10 + s[j] - '0';
                }
                nums.push(x);
                i = j - 1;
            } else if (s[i] == ']') {
                string t;
                while (res.back() != '[') {
                    t += res.back();
                    res.pop_back();
                }
                res.pop_back(); // [出栈
                reverse(begin(t), end(t));
                while (nums.top()-- > 0) {
                    res += t;
                }
                nums.pop(); // 数出栈
            } else { // 字母和[直接压栈
                res += s[i];
            }
        }
        return res;
    }
};

O(n) DFS
用这个

class Solution {
public:
    string decodeString(string s) {
        int i = 0;
        return helper(s, i);
    }

    string helper(const string &s, int &i) {
        string res;
        for (int n = s.length(); i < n && s[i] != ']'; ++i) {
            if (isdigit(s[i])) {
                int num = 0;
                for (; i < n && isdigit(s[i]); ++i) {
                    num = num * 10 + s[i] - '0';
                }
                auto t = helper(s, ++i); // 跳过[
                while (num-- > 0) {
                    res += t;
                }
            } else {
                res += s[i];
            }
        }
        return res;
    }
};

class Solution {
public:
    string decodeString(string s) {
        int i = 0;
        return helper(s, i);
    }

    string helper(const string &s, int &i) {
        string ret;
        while (i < s.length() && s[i] != ']') {
            if (isdigit(s[i])) {
                int num = 0;
                do {
                    num = num * 10 + s[i++] - '0';
                } while (i < s.length() && isdigit(s[i]));
                string t = helper(s, ++i);
                ++i; // 因为helper完最后i会指向上一个]所以需要跳过，放到while循环完最后加也可以
                while (num-- > 0) {
                    ret += t;
                }
            }
            else {
                ret += s[i++];
            }
        }
        return ret;
    }
};