LeetCode - 394. 字符串解码

题目

394. 字符串解码 - 力扣（LeetCode）

思路

使用两个栈：一个存储重复次数，一个存储字符串

遍历输入字符串：

• 数字处理：遇到数字时，累积计算重复次数
• 左括号处理：保存当前状态（入栈），开始处理新的嵌套部分
• 字母处理：直接添加到当前字符串，不涉及栈操作
• 右括号处理：完成当前嵌套部分，应用重复规则，恢复之前的状态（出栈）

最终返回处理后的字符串

该算法能够处理嵌套的编码，例如"2[a2[bc]]"这样的情况。时间复杂度为O(n)，其中n是输入字符串的长度。

过程

• countStack: []

• strStack: []

• currentStr: ""

• count: 0

处理字符 '3'

字符: '3'
操作: 数字 → 更新count = 3
countStack: []
strStack: []
currentStr: ""
count: 3

处理字符 '['

字符: '['
操作: 左括号 → 保存当前状态，重置当前变量
countStack: [3]  ← 入栈
strStack: [""]   ← 入栈
currentStr: ""   ← 重置
count: 0         ← 重置

 处理字符 'a'

字符: 'a'
操作: 字母 → 添加到currentStr
countStack: [3]
strStack: [""]
currentStr: "a"  ← 添加'a'
count: 0

处理字符 ']'

字符: ']'
操作: 右括号 → 出栈并应用重复
countStack: []   ← 弹出3
strStack: []     ← 弹出""
重复计算: "" + "a"*3 = "aaa"
currentStr: "aaa"  ← 更新
count: 0

 处理字符 '2'

字符: '2'
操作: 数字 → 更新count = 2
countStack: []
strStack: []
currentStr: "aaa"
count: 2         ← 更新

  处理字符 '['

字符: '['
操作: 左括号 → 保存当前状态，重置当前变量
countStack: [2]      ← 入栈
strStack: ["aaa"]    ← 入栈
currentStr: ""       ← 重置
count: 0             ← 重置

 处理字符 'b'

字符: 'b'
操作: 字母 → 添加到currentStr
countStack: [2]
strStack: ["aaa"]
currentStr: "b"      ← 添加'b'
count: 0

 处理字符 'c'

字符: 'c'
操作: 字母 → 添加到currentStr
countStack: [2]
strStack: ["aaa"]
currentStr: "bc"     ← 添加'c'
count: 0

 处理字符 ']'

字符: ']'
操作: 右括号 → 出栈并应用重复
countStack: []       ← 弹出2
strStack: []         ← 弹出"aaa"
重复计算: "aaa" + "bc"*2 = "aaa" + "bcbc" = "aaabcbc"
currentStr: "aaabcbc"  ← 更新
count: 0

  处理结束

最终结果: "aaabcbc"

一些难点解读

正确写法

class Solution {
public:
    string decodeString(string s) {
        stack<int> countStack;
        stack<string> strStack; 
        string currentStr = "";
        int count = 0;
        for(int i = 0; i<s.size();i++)
        {
            if(isdigit(s[i]))
            {
                count = count * 10 + (s[i] - '0');
            }
            else if(s[i] == '[')
            {
                countStack.push(count);
                strStack.push(currentStr);
                count = 0;
                currentStr = "";
            }
            else if(s[i] == ']')
            {
                int repeatTimes = countStack.top();
                countStack.pop();

                string decodedStr = strStack.top();
                strStack.pop();

                for(int i = 0; i< repeatTimes; i++)
                {
                    decodedStr += currentStr;
                }

                currentStr = decodedStr;
            }
            else
            {
                currentStr += s[i];
            }
        }
    return currentStr;
    }
};