手帐 Blog

主题

复盘 · LC 394 字符串解码 ​

题目 ​

题意 ​

输入 s 由小写字母、数字和 [] 组成，形如 k[encoded_string]，表示 encoded_string 重复 k 次。数字 k 为正整数，可多位（如 13）。嵌套合法，求解码后的字符串。

  • 约束：1 <= s.length <= 30，嵌套深度有限，但逻辑要处理嵌套与多位数。
  • 边界：无括号纯字母、10[a] 等多位数、3[a2[c]] 嵌套。

涉及算法 ​

标签一句话
栈遇 ] 弹到 [，读出次数，把展开串压回栈
字符串模拟按字符扫，数字累乘、括号分层

教程对照：栈专题 10 · 栈；字符串模拟见 23 · 字符串常考 的「按规则解析」心智。

评价我的解法 ​

你的思路：单栈混存数字字符、[、字母；遇 ] 倒序拼子串，再按次数重复压栈。方向正确，且 LeetCode 能 AC。

我的代码（摘自 394-字符串解码/index.js，不含测例）：

javascript
var decodeString = function (s) {
  const numArr = Array.from({ length: 10 }).fill(0);
  numArr.forEach((item, index) => {
    numArr[index] = String(index);
  });
  let stack = [];
  let i = 0,
    len = s.length;
  for (i = 0; i < len; i++) {
    const char = s[i];
    if (char === "]") {
      let tmpStr = "";
      while (stack.length > 0) {
        const item = stack[stack.length - 1];
        stack.pop();
        if (item === "[") {
          let times = "";
          let last = stack.length - 1;
          while (numArr.includes(stack[last])) {
            times = stack[last] + times;
            stack.pop();
            last = stack.length - 1;
          }
          times = parseInt(times);
          for (let i = 0; i < times; i++) {
            stack.push(tmpStr);
          }
          break;
        } else {
          tmpStr = item + tmpStr;
        }
      }
    } else if (numArr.includes(char)) {
      while (i + 1 < s.length && numArr.includes(s[i])) {
        stack.push(s[i]);
        i++;
      }
      stack.push("[");
    } else {
      stack.push(char);
    }
  }
  return stack.join("");
};

对在哪

  1. 栈处理嵌套：内层先展开，外层再乘次数，顺序对。
  2. 多位数用连续数字字符拼 times，13[abc] 本地与 3[a2[c]] 等测例正确。
  3. 见 ] 时倒序拼 tmpStr，符合「从栈顶往回读」的直觉。

糙在哪

  1. 读数字时手写 [ 进栈：numArr.includes 分支末尾 stack.push("[")，再靠 for 的 i++ 跳过输入里的真 [。能跑，但依赖循环下标与「假括号」配合，可读性和可维护性差，别人很难改。
  2. numArr 判数字：char >= '0' && char <= '9' 或 Number.isDigit 更直接；includes 每次 O(10) 无必要。
  3. 内层 for (let i = 0; ...) 与外层 i 同名：当前作用域不冲突，但增加误改风险。
  4. 重复压栈：times 次 push(tmpStr) 在次数大时字符串拼接成本高；标准写法用 str.repeat(times) 一次生成。
  5. 若 [ 与数字栈状态不一致，parseInt('') 得 NaN，展开会静默失败——目前靠下标跳过躲开了，属于侥幸而非结构保证。

复杂度：每个字符入栈、出栈常数次 → 时间 O(n)；空间 O(n)。常数因子偏大。

最佳题解 ​

**双栈（数字栈 + 字符串栈）**或单循环里 num / prevStr / curStr——模板清晰，不伪造 [：

javascript
/**
 * @param {string} s
 * @return {string}
 */
var decodeString = function (s) {
  const nums = [];
  const strs = [];
  let num = 0;
  let str = "";

  for (const ch of s) {
    if (ch >= "0" && ch <= "9") {
      num = num * 10 + Number(ch);
    } else if (ch === "[") {
      nums.push(num);
      strs.push(str);
      num = 0;
      str = "";
    } else if (ch === "]") {
      const repeat = nums.pop();
      const prev = strs.pop();
      str = prev + str.repeat(repeat);
    } else {
      str += ch;
    }
  }
  return str;
};
  • 时间 O(n)，空间 O(n)。
  • 为何更优：遇 [ 保存外层状态、遇 ] 一层结算；不混用栈元素类型，面试口述四步即可画出来。

关联题目 ​

题为何相关
20. 有效的括号栈 + 括号配对入门
227. 基本计算器 II表达式栈模拟
385. 迷你语法分析器嵌套结构递归/栈

一句话带走 ​

字符串解码：扫到数字累乘、遇 [ 把次数和当前串存档、遇 ] 用 外层串 + 内层串.repeat(k) 回退一层。