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;}
};