題目描述
給定一個經(jīng)過編碼的字符串训桶，返回它解碼后的字符串匿刮。
編碼規(guī)則為: k[encoded_string]焦履，表示其中方括號內(nèi)部的 encoded_string 正好重復(fù) k 次到推。注意 k 保證為正整數(shù)床三。
你可以認為輸入字符串總是有效的；輸入字符串中沒有額外的空格月趟，且輸入的方括號總是符合格式要求的灯蝴。
此外，你可以認為原始數(shù)據(jù)不包含數(shù)字孝宗，所有的數(shù)字只表示重復(fù)的次數(shù) k 穷躁，例如不會出現(xiàn)像 3a 或 2[4] 的輸入。
示例:
s = "3[a]2[bc]", 返回 "aaabcbc".
s = "3[a2[c]]", 返回 "accaccacc".
s = "2[abc]3[cd]ef", 返回 "abcabccdcdcdef".
分析
使用棧保存當前正在處理的編碼字符串因妇。
保存編碼字符串的次數(shù)和前綴
遇到]符號后问潭，把棧頂?shù)臄?shù)據(jù)取出來出來
使用string的append函數(shù)添加字符串
代碼
class Solution {
public:
string decodeString(string s) {
string res;
if(s.empty()) {
return res;
}
stack<pair<int, string>> st;
string num;
string encode;
for(int i = 0; i < s.length(); i++){
if(s[i] >= '0' && s[i] <= '9') {
num += s[i];
} else if(s[i] == '[') {
int n = atoi(num.c_str());
st.push(make_pair(n, encode));
num = "";
encode = "";
} else if(s[i] == ']') {
auto t = st.top();
int n = t.first;
string decode = t.second;
for(int i = 0; i < n; i++) {
decode.append(encode);
}
st.pop();
if(st.empty()) {
res.append(decode);
encode = "";
} else {
encode = decode;
}
} else {
encode.append(1,s[i]);
}
}
res.append(encode);
return res;
}
};
