394. 字符串解码
3 min
题目
解法：栈模拟
思路
核心思想：使用栈模拟解码过程，遇到’]‘时从栈中取出字符串和重复次数，展开后再压入栈中。
正确性证明：栈的后进先出特性保证了嵌套结构的正确处理。当遇到’]‘时，栈顶元素必然是最近未匹配的’[‘之后的字符串，通过弹出并计算重复次数，可以正确展开每一层嵌套。每次解码后将结果重新压栈，保持了字符串的连续性和正确顺序。
实现步骤：
- Step 1: 遍历字符串，将非’]‘字符压入栈中
- Step 2: 遇到’]‘时，从栈顶弹出字符直到’[‘，得到encoded_string
- Step 3: 弹出’[‘后，从栈顶弹出数字计算重复次数k
- Step 4: 将encoded_string反转并重复k次，将结果重新压入栈中
- Step 5: 遍历结束后，将栈中所有字符弹出并反转得到最终结果
复杂度
- 时间复杂度: ，其中n为输入字符串长度，每个字符最多入栈出栈一次
- 空间复杂度: ，栈最多存储所有字符
代码
class Solution {
public:
string decodeString(string s) {
stack<char>st;
for(auto i:s){
if(i!=']'){
st.push(i);
}else{
string s ="";
while(st.top()!='['){
s+=st.top();
st.pop();
}
st.pop();
int num = 0;
int base = 1;
while(!st.empty() && isdigit(st.top())){
num = (st.top()-'0') * base + num;
base *= 10;
st.pop();
}
reverse(s.begin(),s.end());
string tmp;
while(num--){
class Solution {
public:
string decodeString(string s) {
stack<char>st;
for(auto i:s){
if(i!=']'){
st.push(i);
}else{
string s ="";
while(st.top()!='['){
s+=st.top();
st.pop();
}
st.pop();
int num = 0;
int base = 1;
while(!st.empty() && isdigit(st.top())){
num = (st.top()-'0') * base + num;
base *= 10;
st.pop();
}
reverse(s.begin(),s.end());
string tmp;
while(num--){
tmp+=s;
}
for(auto j:tmp)
st.push(j);
}
}
string ans = "";
while(!st.empty()){
ans+=st.top();
st.pop();
}
reverse(ans.begin(),ans.end());
return ans;
}
};