394.字符串解码

字符串解码

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

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

示例 1：

输入：s = “3[a]2[bc]”
输出：”aaabcbc”

示例 2：

输入：s = “3[a2[c]]”
输出：”accaccacc”

示例 3：

输入：s = “2[abc]3[cd]ef”
输出：”abcabccdcdcdef”

提示：

• 1 <= s.length <= 30
• s 由小写英文字母、数字和方括号 ‘[]’ 组成
• s 保证是一个 有效 的输入
• s 中所有整数的取值范围为 [1, 300]

解析

用栈来处理嵌套结构。

/**
 * @param {string} s
 * @return {string}
 */
var decodeString = function (s) {
  const numStack = [];
  const strStack = [];
  let currentStr = "";
  let currentNum = 0;

  for (const ch of s) {
    if (ch >= "0" && ch <= "9") {
      currentNum = currentNum * 10 + Number(ch);
    } else if (ch === "[") {
      numStack.push(currentNum);
      strStack.push(currentStr);
      currentNum = 0;
      currentStr = "";
    } else if (ch === "]") {
      const num = numStack.pop();
      const prevStr = strStack.pop();
      currentStr = prevStr + currentStr.repeat(num);
    } else {
      currentStr += ch;
    }
  }
  return currentStr;
};

遇到 [ 就把当前状态压栈，遇到 ] 就弹栈并重复拼接。完美处理嵌套情况。