题目描述
Given an encoded string, return its decoded string.
The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times. Note that k is 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 like 3a or 2[4].
Example:
s = “3[a]2[bc]”, return “aaabcbc”.
s = “3[a2[c]]”, return “accaccacc”.
s = “2[abc]3[cd]ef”, return “abcabccdcdcdef”.
0306刷题
- 可以举 3[a2[c]] 这个例子
- 用 stack 来辅助运算，我们用两个 stack，一个用来保存个数，一个用来保存字符串
- 我们遍历输入字符串，如果遇到数字，我们更新计数变量 cnt；
- 如果遇到左括号，我们把当前 cnt 压入数字栈中，把当前t压入字符串栈中；3[a2[ // 这里res = a, 然后把res压入栈，然后清空res
- 如果遇到右括号时，我们取出数字栈中顶元素，存入变量k，然后给字符串栈的顶元素循环加上k个t字符串，// a + c + c， ，更新top， 然后更新res，pop
- 然后取出顶元素存入字符串t中；如果遇到字母，我们直接加入字符串t中即可，
class Solution {
public:
string decodeString(string s) {
stack<int> s_num;
stack<string> s_str;
int cnt = 0;
string res;
for(int i = 0; i < s.size(); i++){
if(s[i] >= '0' && s[i] <= '9'){
cnt = cnt * 10 + s[i] - '0';
}else if(s[i] == '['){
s_num.push(cnt);
cnt = 0;
s_str.push(res);
res = "";
}else if(s[i] == ']'){
int k = s_num.top();
s_num.pop();
for(int i = 0; i < k; i++){
s_str.top() += res; // 给s_top进行赋值，当s_top为空时，可以更新为k倍的res
}
res = s_str.top();
s_str.pop();
}else{
res += s[i];
}
}
return res;
}
};
解题思路
- 分为数字栈和字符栈
- 每次如果数字的话，就进入数字栈
- 如果是字符的话，看是否为’]’字符，如果为’]’字符，就要进行解析（这里有一点，由于数字栈可能会有多位，这里写的是如果是遇到了’[‘,标志着一个重复数字的结束，往数字栈加入一个’-1’）
- 解析的过程为，逐个弹出字符栈，直至为’[‘,进行组合
- 这里如果字符栈仍不为空，证明有嵌套的形式，需要将上步组合的结果重新压入字符栈（等于有一点去括号的过程）
- 如果字符栈为空了，生成最后的结果
- 这里注意一点，会有2[ab]3[cd]ef这种情况
- 剩下的还要加上字符栈剩余的问题
- 测试样例 2[ab]3[cd]， 2[ab3[a]cd], 2[ab]3[cd]ef， 200[ab]300[cd]ef三种情况
C++代码
class Solution {
public:
stack<char> s1;
stack<int> s2;
string decodeString(string s) {
string res = "";
for(int i = 0; i < s.size(); i++){
if(s[i] >= '0' && s[i] <= '9'){
s2.push(s[i] - '0');
continue;
}
if(s[i] == '['){
s2.push(-1);
}
if(s[i] != ']'){
s1.push(s[i]);
}else{
int num = fun_helper();;
string t = "";
while(s1.top() != '['){
t = s1.top() + t;
s1.pop();
}
if(s1.top() == '['){
s1.pop();
}
if(!s1.empty()){
for(int j = 0; j < num; j++){
for(int i = 0; i < t.size(); i++){
s1.push(t[i]);
}
}
}else{
for(int i = 0; i < num; i++){
res += t;
}
}
}
}
string t = "";
while(!s1.empty()){
t = s1.top() + t;
s1.pop();
}
res += t;
return res;
}
int fun_helper(){
int res = 0;
s2.pop();
int i = 0;
while(!s2.empty() && s2.top() != -1){
res += s2.top() * pow(10,i);
s2.pop();
i++;
}
return res;
}
};
