用两个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;
