字符串解码与路径规整

如何展开形如 k[encoded] 的字符串？

• 做法 (394): 用 resStack 保存左括号之前已解码的片段, numStack 保存左括号之前的重复次数;
• 遇数字: 累加到 num (处理多位数);
• 遇 [: 把当前 res、num 入栈, 然后清零, 开始解码新一层;
• 遇 ]: 弹出外层片段与次数, 拼接成 外层 + 内层 × 次数;
• 遇字母: 追加到当前 res;

const decodeString = (s) => {
  const resStack = [];
  const numStack = [];
  let res = "";
  let num = 0;
  for (const c of s) {
    if (/\d/.test(c)) {
      num = num * 10 + Number(c);
    } else if (c === "[") {
      resStack.push(res);
      numStack.push(num);
      res = "";
      num = 0;
    } else if (c === "]") {
      res = resStack.pop() + res.repeat(numStack.pop());
    } else {
      res += c;
    }
  }
  return res;
};

• 时间 $O(n)$, 空间 $O(n)$;

如何把路径规整为最简形式？

• 规则 (71): 多个 / 视为一个; . 表示当前目录, 忽略; .. 回到上一级, 没有上一级则留在根;
• 做法: 按 / 切分并过滤空串, 用栈保存目录名; 遇 .. 弹栈, 其余压栈;
• 结果: "/" + stack.join("/");

const simplifyPath = (path) => {
  const parts = path.split("/").filter((value) => value.length !== 0);
  const stack = [];
  for (const part of parts) {
    if (part === ".") continue;
    if (part === "..") stack.pop();
    else stack.push(part);
  }
  return "/" + stack.join("/");
};

如何删除字符串中的全部相邻重复项？

• 做法 (1047): 从左到右扫描, 当前字符与栈顶相同就弹出栈顶, 否则压栈;
• 正确性: 每次消去一对后, 新的栈顶可能与后续字符再次相邻, 而栈结构天然保留了这种可能;
• 结果: stack.join("");

const removeDuplicates = (s) => {
  const stack = [];
  for (const ch of s) {
    if (ch === stack.at(-1)) stack.pop();
    else stack.push(ch);
  }
  return stack.join("");
};