394. Decode String

用两个stack，一个stack存repetition num(count), 一个stack存已经decode好的string. 几个keys:

• 可以把每一个[]里的string看成单独的完整string block. 比如2[a]里的a是一个完整block， 3[a2[c]]里的c和acc也是完整的string block.
• 见到[: 说明又将有新的string block了，必须把之前的current string存进stack里准备之后衔接不同blocks调用；并且因为有新的block需要解码，必须把currentString的值抹掉(赋为"");
• 见到]: 说明一个完整的string block被读完了，应该把之前存在stack里的decode好的string读出来衔接该block更新currentString
• currentString就是我们最后decode出来的完整string

class Solution {
public:
   
    stack<int> counts;
    stack<string> decodedStrings;
    int count = 0;
    string currentString;
    
    string decodeString(string s) {
        for (char ch : s){
            if (isdigit(ch)){
                count = count*10 + ch - '0';
            } else if (ch == '['){
                counts.push(count);
                count = 0;
                decodedStrings.push(currentString);
                currentString = "";
            } else if (ch == ']'){
                string decodedString = decodedStrings.top();
                decodedStrings.pop();
                for (int i = 0; i < counts.top(); i++){
                    decodedString += currentString;
                }
                counts.pop();               
                currentString = decodedString;
            } else {
                currentString += ch;
            }
        }
        return currentString;
    }
};


// Input: s = "3[a]2[bc]"
// Output: "aaabcbc"
    
    
// Input: s = "3[a2[c]]"
// Output: "accaccacc"   

Time complexity: O(max(count)*length(s))

Space complexity: O(m+n)
m: # of digits in s;
n: # of letters in s;