字符串解码

题目

题目来源：力扣（LeetCode）

给定一个经过编码的字符串，返回它解码后的字符串。
编码规则为: 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”

思路分析

我们使用两个栈来维护我们需要的元素，其中一个栈维护字符串，另一个栈维护数字。

遍历整个字符串：

当遇到左中括号 “[“ 时，将当前已经获取到的字符串和数字分别压入对应的栈中，然后重置已经获得的字符串以及数字。

当遇到右中括号 “]” 时，就分别从两个栈顶取出字符串即数字，然后对字符串进行循环拼接，然后将拼接好的字符串赋值给我们的结果字符串。

当遇到字符串的时候，就对字符串进行拼接，遇到数字的时候，就将数字记录起来。

最后当完成循环的时候，字符串也就已经拼接完成了。

/**
 * @param {string} s
 * @return {string}
 */
var decodeString = function(s) {
  const numStack = [];   // 维护数字的栈
  const strStack = [];   // 维护字符串的栈
  let num = 0; 
  let result = '';
  for (const char of s) { // 遍历字符串
    // 当前字符为 数字
    if (!isNaN(char)) {
      num = num * 10 + Number(char); // 算出倍数
    }
    // 当前字符为左中括号 "[" , 字符串和数字分别入栈   
    else if (char === '[') {
      strStack.push(result); // result 字符串入栈
      result = '';           // 入栈后清空
      numStack.push(num);    // 倍数 num 入栈
      num = 0;               // 入栈后置为 0 
    }
    // 当前字符为右中括号 "]", 字符串和数字分别出栈
    else if (char === ']') {
      const repeatTimes = numStack.pop();
      // 拼接字符串
      result = strStack.pop() + result.repeat(repeatTimes);
    }
    // 当前为字符为字符串
    else {
      result += char; // 拼接字符
    }
  }
  return result
};