字符串解码 3[a2[c]] 怎样用栈做？

简答

LeetCode 394 的规则是 k[encoded_string] 表示方括号里的内容重复 k 次，可以嵌套。比如 3[a]2[bc] 解成 aaabcbc，3[a2[c]] 先把里面的 a2[c] 解成 acc，再重复 3 次得到 accaccacc。

难点是嵌套：读到内层括号时，外层的内容还没拼完，要先放到一边，等内层解完再接回去。这种“先进去的后处理”正好是栈的特点。

具体做法是一边遍历一边维护两个值：当前拼出来的字符串 current 和正在读的数字 num。遇到数字就 num = num * 10 + 数字，因为次数可能有多位，比如 100；遇到 [ 就把 current 和 num 压栈，再把两者清空，开始拼括号里的内容；遇到 ] 就弹出栈顶，结果是“弹出的前缀 + current 重复 k 次”；遇到字母直接拼到 current 后面。

题目保证输入合法，数字只用来表示重复次数，所以不用处理括号不匹配或 3a 这样的情况。时间复杂度和解码后的字符串长度成正比，栈的深度等于括号嵌套层数。

用栈解码

function decodeString(s) {
  const stack = [];
  let current = '';
  let num = 0;

  for (const ch of s) {
    if (ch >= '0' && ch <= '9') {
      // 次数可能是多位数，比如 12[a]
      num = num * 10 + Number(ch);
    } else if (ch === '[') {
      stack.push([current, num]);
      current = '';
      num = 0;
    } else if (ch === ']') {
      const [prefix, times] = stack.pop();
      current = prefix + current.repeat(times);
    } else {
      current += ch;
    }
  }
  return current;
}

console.log(decodeString('3[a]2[bc]')); // aaabcbc
console.log(decodeString('3[a2[c]]')); // accaccacc
console.log(decodeString('2[abc]3[cd]ef')); // abcabccdcdcdef
console.log(decodeString('12[x]').length); // 12

以 3[a2[c]] 为例走一遍。读到 3，num 是 3；读到 [，把 ['', 3] 压栈，current 清空；读到 a，current 是 a；读到 2 和 [，把 ['a', 2] 压栈，current 又清空；读到 c，current 是 c。

接着第一个 ] 弹出 ['a', 2]，current 变成 'a' + 'cc'，也就是 acc。第二个 ] 弹出 ['', 3]，current 变成 '' + 'acc'.repeat(3)，得到 accaccacc。

为什么压栈时要把 current 一起存起来？因为 [ 之前拼好的部分是外层的前缀，内层解完以后要接在它后面。不存的话，清空 current 时这部分就丢了。为什么 num 也要清零？因为括号里面可能还有自己的数字，不清零就会和外层的次数连成一个数。

也可以用递归

每遇到一个 [ 就相当于进入一个子问题，所以也可以写成递归：函数负责解码到对应的 ] 为止，返回解好的字符串和读到的位置。递归用的是调用栈，思路和显式栈一样。显式栈的好处是嵌套很深时不会受调用栈深度的限制，LeetCode 394 限制输入长度不超过 30，两种写法都没问题。栈的其他基础题见《有效括号、最小栈这类栈题怎样做？》。

常见追问

为什么数字要用 num * 10 + 数字 累加？

因为重复次数可能是多位数，LeetCode 394 的次数范围是 1 到 300。逐个字符读的时候，12 会先读到 1 再读到 2，乘 10 再加才能还原成 12。

能不能用正则反复替换最内层的括号？

可以。每次用正则匹配不含括号的 数字[字母]，替换成展开后的字符串，直到没有括号。这种写法简短，但每轮都要扫描整串并生成新字符串，嵌套层数多时比一次遍历慢。面试里一般先写栈的版本。