0394-字符串解码.md

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

编码规则为: 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"

var decodeString = function(s) {
  const stack = []
  let i = 0

  while(i < s.length) {
    const cur = s[i]
    if (cur === ']') {
      let j = stack.length - 1
      let temp = ''
      while(j > 0) {
        const pop = stack.pop()
        if (pop === '[') {
          let k = stack.length - 1
          let times = ''
          while(k >= 0) {
            if (isNaN(Number(stack[k]))) {
              break;
            } else {
              times = stack.pop() + times
              k--
            }
          }
          stack.push(temp.repeat(Number(times)))
          temp = ''
          break
        } else {
          temp = pop + temp
          j++
        }
      }
    } else {
      stack.push(cur)
    }
    i++
  }

  return stack.join('')
};

解题思路：循环入栈，遇到]时候，记录下遇到[之间的字符，然后再while循环一次寻找前面的数字，记录为times，最后将字符重复times次push入栈，继续循环。最后输出栈内文字即可。