用兩個stack，一個stack存repetition num(count), 一個stack存已經(jīng)decode好的string. 幾個keys:
- 可以把每一個[]里的string看成單獨的完整string block. 比如2[a]里的a是一個完整block毅人， 3[a2[c]]里的c和acc也是完整的string block.
- 見到[: 說明又將有新的string block了售貌，必須把之前的current string存進stack里準(zhǔn)備之后銜接不同blocks調(diào)用咐鹤；并且因為有新的block需要解碼粘茄，必須把currentString的值抹掉(賦為"");
- 見到]: 說明一個完整的string block被讀完了霸旗，應(yīng)該把之前存在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;
