394.字符串解码

394.字符串解码

Category	Difficulty	Likes	Dislikes
algorithms	Medium (56.37%)	1221	-

Tags
Companies
给定一个经过编码的字符串，返回它解码后的字符串。
编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。

示例 1：
输入：s = “3[a]2[bc]” 输出：“aaabcbc”
示例 2：
输入：s = “3[a2[c]]” 输出：“accaccacc”
示例 3：
输入：s = “2[abc]3[cd]ef” 输出：“abcabccdcdcdef”
示例 4：
输入：s = “abc3[cd]xyz” 输出：“abccdcdcdxyz”

提示：

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

---

Discussion | Solution

思路

两个栈分别维护数字和括号，在括号尾时，括号栈及数字栈出栈入配对队列。配对队列出队拿到对应的重复的次数及字符串，用 replaceAll 替换所有字符，最后返回结果即可。

解答

/*
 * @lc app=leetcode.cn id=394 lang=javascript
 *
 * [394] 字符串解码
 */

// @lc code=start
/**
 * @param {string} s
 * @return {string}
 */
var decodeString = function (s) {
  let res = s;
  const stack = [],
    pair = [],
    numStack = [];

  const reg = /[0-9]/;

  let num = "";

  for (let i = 0; i < s.length; i++) {
    const char = s[i];
    if (reg.test(char)) {
      num += char;
    }
    if (char === "[") {
      stack.push({ value: "[", index: i });
      numStack.push(num);
      num = "";
    } else if (char === "]") {
      const top = stack.at(-1);
      if (top.value === "[") {
        pair.unshift([+numStack.pop(), top.index, i]);
        stack.pop();
      }
    }
  }

  while (pair.length) {
    const [times, l, r] = pair.shift();
    const word = s.slice(l + 1, r);
    const replaceStr = `${times}[${word}]`;
    const str = new Array(+times).fill(word).join("");
    res = res.replaceAll(replaceStr, str);
  }

  return res;
};
// @lc code=end