394. Decode String

Given an encoded string, return it's decoded string.

The encoding rule is:k[encoded_string], where theencoded_stringinside the square brackets is being repeated exactlyktimes. Note thatkis guaranteed to be a positive integer.

You may assume that the input string is always valid; No extra white spaces, square brackets are well-formed, etc.

Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers,k. For example, there won't be input like3aor2[4].

Examples:

s = "3[a]2[bc]", return "aaabcbc".
s = "3[a2[c]]", return "accaccacc".
s = "2[abc]3[cd]ef", return "abcabccdcdcdef".

S1： stack O(n)

用两个stack 存储repeat次数和当前string。每次遇到’]'计算string栈顶元素并下推一层

class Solution {
public:
    string decodeString(string s) {
        string result = "";
        string str = "";
        string digit = "";
        stack_s.push("");
        for (int i = 0; i < s.size(); i++) {
            if (s[i] >= '0' && s[i] <= '9') {             
                digit += s[i];
            } else if (s[i] == '[') {
                stack_k.push(stoi(digit));
                stack_s.push("");
                digit = "";
            } else if (s[i] == ']') {
                str = stack_s.top();
                stack_s.pop();
                for (int i = stack_k.top(); i > 0; i--) {
                    stack_s.top() += str; 
                }
                stack_k.pop();                
            } else {
                stack_s.top() += s[i];
            }
        }
        return stack_s.top();
    }

private:
    stack<int> stack_k;
    stack<string> stack_s;
};

S2： recursion

遇到[就进入下一层，遇到]返回上一层。recursion层数比较多会慢

    string decodeString(string s) {
        int i = 0;
        return getDecode(s, i);
    }

    string getDecode(string s, int& i) {
        string result = "";
        string digit = "";
        while (i < s.size()) {
            if (s[i] == '[') {
                string str = getDecode(s, ++i);
                for (int i = stoi(digit); i > 0; --i) {
                    result += str;
                }
                digit = "";
            } else if (s[i] == ']') {
                i++;
                return result;
            } else if (isdigit(s[i])) {
                digit += s[i++];
            } else {
                result += s[i++]; 
            }
        }
        return result;
    }