字符串解码

更新: 7/4/2026 字数: 0 字 时长: 0 分钟

题目描述

给定一个经过编码的字符串，按照编码规则将其解码还原。本文覆盖两种常见形态：

变体一 · 带括号（LeetCode 394）

编码规则为 k[encoded_string]，表示方括号内部的 encoded_string 正好重复 k 次。k 为正整数，括号可以任意嵌套。

输入："3[a2[c]]" → 输出："accacc" 输入："3[a]2[bc]" → 输出："aaabcbc" 输入："2[abc]3[cd]ef" → 输出："abcabccdcdcdef"

变体二 · 不带括号（游程 / 紧邻式）

编码规则为「字母 + 紧跟的数字」表示该字母连续重复的次数，没有任何括号与嵌套，本质是游程编码 (Run-Length Encoding) 展开。

输入："a3b2c1" → 输出："aaabbc" 输入："a2b1c5a3" → 输出："aabcccccaaa"

思路拆解

变体二（不带括号）：一次扫描即可

没有括号意味着没有嵌套——重复的作用域仅限于紧挨在数字前面的那一个字母。于是只需要线性扫描：遇到字母先记住它，遇到数字就累积重复次数（注意可能是多位数），当一个「字母 + 数字」单元读完时，把字母重复对应次数追加到结果里即可。

核心思路

不带括号的版本不需要任何栈，因为作用域是平的。真正的难点全部集中在带括号的嵌套版本上——那才是本题的主角。

变体一（带括号）：为什么会想到栈？

暴力递归的直觉：看到 k[...] 就先把括号内部递归解码成一个字符串 t，再把 t 重复 k 次。嵌套天然对应递归——内层先算完，外层再拿结果去重复。这条路完全可行，但每次都要定位与之匹配的右括号，实现起来容易在下标上出错。

从递归到栈：递归的本质是「先挂起外层的未完成状态，进入内层，内层算完再恢复外层」。这个「挂起—恢复」正是栈的语义。于是我们把递归改写成显式的双栈迭代：

• numStack（次数栈）：进入一层括号前，把当前累积的重复次数 k 压进去；
• strStack（前缀栈）：进入一层括号前，把「括号左边已经拼好的字符串」压进去；
• cur（当前层）：正在构建的这一层字符串；
• num（当前数字）：正在解析的重复次数（支持多位数）。

扫描时对四种字符分别处理：

1. 数字：num = num * 10 + d，累积成完整的（可能多位）重复次数；
2. [：把 num 压入 numStack、把 cur 压入 strStack，然后把 num、cur 清零/清空，进入新的一层；
3. ]：一层结束。弹出次数 k = numStack.pop()、弹出前缀 prefix = strStack.pop()，令 cur = prefix + cur.repeat(k)——即把刚构建完的这一层重复 k 次，再拼回它的前缀；
4. 字母：直接追加到 cur。

关键不变量

无论嵌套多深，cur 永远表示「当前所在括号层、到目前为止已经拼好的字符串」。遇到 ] 时，cur 恰好是该层完整内容，弹栈拼接即可回到上一层。

下面的交互动画完整演示带括号版本对 "3[a2[c]]" 的双栈解码过程，可单步、自动播放与重置：

双栈法 · 字符串解码演示

样例输入："3[a2[c]]"

30

[1

a2

23

[4

c5

]6

]7

numStack（次数）

空

strStack（前缀）

空

num0

cur（当前层）""

双栈法：numStack 存重复次数，strStack 存外层已累积的字符串。cur 是当前层正在构建的串，num 是正在解析的数字。

步骤 0 / 9

完整代码

变体一 · 带括号（双栈，最优）

/**
 * @param {string} s 形如 "3[a2[c]]" 的编码串
 * @return {string} 解码结果，如 "accacc"
 */
function decodeString(s) {
  const numStack = []   // 次数栈：保存外层待重复的 k
  const strStack = []   // 前缀栈：保存外层已拼好的字符串
  let cur = ''          // 当前层正在构建的字符串
  let num = 0           // 当前正在解析的重复次数（可多位）

  for (const ch of s) {
    if (ch >= '0' && ch <= '9') {
      num = num * 10 + (ch.charCodeAt(0) - 48) // 多位数累积
    } else if (ch === '[') {
      numStack.push(num) // 挂起外层次数
      strStack.push(cur) // 挂起外层前缀
      num = 0            // 进入新一层，清零
      cur = ''
    } else if (ch === ']') {
      const k = numStack.pop()      // 本层重复次数
      const prefix = strStack.pop() // 本层左侧前缀
      cur = prefix + cur.repeat(k)  // 重复后拼回前缀
    } else {
      cur += ch          // 普通字母，追加到当前层
    }
  }
  return cur
}

变体一 · 带括号（递归解法，等价思路）

点击展开递归解法

function decodeString(s) {
  let i = 0
  function dfs() {
    let res = ''
    let num = 0
    while (i < s.length && s[i] !== ']') {
      const ch = s[i]
      if (ch >= '0' && ch <= '9') {
        num = num * 10 + (+ch)
        i++
      } else if (ch === '[') {
        i++                 // 跳过 '['
        const inner = dfs() // 递归解码内层
        res += inner.repeat(num)
        num = 0
        i++                 // 跳过 ']'
      } else {
        res += ch
        i++
      }
    }
    return res
  }
  return dfs()
}

变体二 · 不带括号（游程展开）

/**
 * "a3b2c1" -> "aaabbc"
 * 规则：每个字母后紧跟它重复的次数（可多位）
 */
function expandRunLength(s) {
  let res = ''
  let i = 0
  while (i < s.length) {
    const ch = s[i++]        // 取字母
    let num = 0
    while (i < s.length && s[i] >= '0' && s[i] <= '9') {
      num = num * 10 + (+s[i++]) // 累积多位数字
    }
    res += ch.repeat(num || 1) // 无数字时默认 1 次
  }
  return res
}

复杂度分析

设 为输入串长度， 为解码后输出串长度。

解法	时间复杂度	空间复杂度	说明
带括号 · 双栈			每个输出字符只被拼接常数次；栈深与嵌套层数成正比
带括号 · 递归			递归栈深度 = 嵌套层数；逻辑等价于双栈
不带括号 · 游程展开			单次线性扫描

复杂度以输出规模 计更准确：因为 3[100[a]] 这类输入的输出可能远大于 ，展开代价由 主导，而非输入长度 。

边界与易错点

易错点

1. 多位数字：k 可能是 10、100，必须用 num = num * 10 + d 累积，不能只读单个字符。
2. 进入括号前要先保存再清零：遇到 [ 时，务必先 push(num)、push(cur)，再把 num、cur 清零/清空。顺序错了会丢失外层状态。
3. 弹栈顺序：遇到 ] 时先弹 numStack 得到 k，再弹 strStack 得到前缀，cur = prefix + cur.repeat(k)——前缀在前、重复结果在后，写反会得到错误顺序。
4. cur 不能提前重置：只有在 [ 处才清空 cur，普通字母要持续累加，否则同一层的多个字母会丢失。
5. 不带括号变体的默认次数：题面若允许字母后无数字（如 "ab3" 中的 a），需按 1 次处理（num || 1），避免漏字符。
6. 嵌套深度：递归解法在极深嵌套时可能栈溢出，双栈迭代法更稳健，工程中优先选用。

一句话总结

带括号看到「嵌套 + 挂起/恢复」就用双栈；不带括号是平的作用域，一次线性扫描即可。