.jpg)
604 字
3 分钟
字符串解码
题目描述
给定一个经过编码的字符串，返回它解码后的字符串。
编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。
测试用例保证输出的长度不会超过 105。
解题思路
- 双栈辅助解析：
- 数字栈：存储重复次数（处理多位数）
- 字符串栈：存储外层字符串片段
- 遍历状态管理：
- 遇到数字：解析完整数字入栈
- 遇到
[：将当前字符串入栈，清空临时串 - 遇到
]：弹出数字和字符串，重复当前串并拼接到外层 - 遇到字母：直接追加到当前串
- 多层嵌套处理：
- 内层括号展开后自动拼接外层片段
- 栈结构天然支持嵌套层级
关键洞察
- 栈匹配原理：
[和]成对出现，栈深度对应嵌套层级- 弹出时自动关联对应数字和字符串片段
- 数字多字节处理：
- 连续数字字符需拼接为整数（“12” → 12）
- 避免将多位数拆分为单数字
- 临时字符串作用：
- 存储当前层级待重复的字符串
- 遇到
[时保存现场，遇到]时展开
- 结果拼接方向：
- 内层展开结果拼接在外层字符串后
- 符合从左到右解码顺序
复杂度分析
| 指标 | 说明 |
|---|---|
| 时间复杂度 | O(S)：S为解码后字符串长度（每个字符生成一次） |
| 空间复杂度 | O(S)：栈空间最坏O(n) + 结果字符串O(S)（n为输入长度） |
代码实现
/** * @param {string} s * @return {string} */var decodeString = function (s) {
const numStack = [], strStack = []; let currentNum = 0, currentStr = '';
for (const char of s) { if (/\d/.test(char)) { currentNum = currentNum * 10 + Number(char); } else if (char === '[') { numStack.push(currentNum); strStack.push(currentStr); currentNum = 0; currentStr = ''; } else if (char === ']') { const repeatTime = numStack.pop(); currentStr = strStack.pop() + currentStr.repeat(repeatTime); } else { currentStr += char; } }
return currentStr;};