算法 - 字符串解码（Decode String）

1. 题目

给定一个经过编码的字符串，返回它解码后的字符串。

编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。

你可以认为输入字符串总是有效的，输入中没有额外的空格，且方括号内总是含有小写字母或另外一个方括号。

示例:

输入: s = "3[a]2[bc]"    输出: "aaabcbc"
输入: s = "3[a2[c]]"    输出: "accaccacc"
输入: s = "2[abc]3[cd]ef" 输出: "abcabccdcdcdef"

2. 解题思路

存在嵌套结构 k[...]，天然适合栈（或递归 DFS）。

2.1 双栈法（数字栈 + 字符串栈）

用两个栈分别保存括号层的「重复次数」和「进入括号前已拼好的字符串」：

• curStr 累积当前层字符串，num 累积当前解析的数字。

• 遇到 [：把当前的 num 压入 numStack、当前 curStr 压入 strStack，然后清空 num 和 curStr，进入内层。

• 遇到 ]：弹出内层重复次数 k 和「外层字符串」prev，令 curStr = prev + curStr.repeat(k)，回到外层。

• 遇到字母：拼进 curStr；遇到数字：num = num * 10 + d（处理多位数）。

• 时间复杂度：O(输出长度)，空间复杂度：O(嵌套深度)。

3. TypeScript 实现

3.1 双栈

function decodeString(s: string): string {
    const numStack: number[] = [];
    const strStack: string[] = [];
    let curStr = "";
    let num = 0;

    for (const ch of s) {
        if (ch >= "0" && ch <= "9") {
            num = num * 10 + Number(ch);      // 多位数字
        } else if (ch === "[") {
            numStack.push(num);               // 保存本层重复次数
            strStack.push(curStr);            // 保存进入括号前的字符串
            curStr = "";
            num = 0;
        } else if (ch === "]") {
            const k = numStack.pop()!;
            const prev = strStack.pop()!;
            curStr = prev + curStr.repeat(k); // 内层展开并拼接外层
        } else {
            curStr += ch;                      // 普通字母
        }
    }

    return curStr;
}

console.log(decodeString("3[a2[c]]")); // accaccacc

3.2 单栈（把字符逐个压栈）

把 ] 之前的所有字符压栈，遇到 ] 时弹栈收集字母与数字，再展开重新压回。写法统一但弹栈拼接略繁。

4. 面试延伸

• 递归解法：用全局指针 i，decode() 遇到 [ 递归取内层结果并 repeat，遇到 ] 返回——很多前端候选人觉得递归更直观。
• 本题是「括号匹配 / 嵌套求值」家族，同族：基本计算器、有效括号、最小栈。看到「嵌套 + 需要回到上一层状态」就应条件反射想到栈/递归。
• 坑点：数字可能是多位（如 12[a]），必须用 num = num*10 + d 累积，不能 Number(ch) 单独取。

难度：中等 | LeetCode 394 | 栈 / 递归