栈

[now915]

栈

var decodeString = function(s) {
  let index = 0
  const stack = []
  function getNumber(str) {
    let num = 0
    while (/\d/.test(Number(str[index]))) {
      num = num*10 + Number(str[index])
      index++
    }
    return num
  }

  while(index < s.length){
    if (/[0-9]/.test(Number(s[index]))) {
      stack.push(getNumber(s))
    } else if (/[A-Za-z]/.test(s[index])) {
      stack.push(s[index])
      index++
    } else if (s[index] === '[') {
      index++
    } else {
      // 出栈
      // 获取字符串
      let tmp = ''
      while (stack.length && /[A-Za-z]/.test(stack[stack.length-1])) {
        tmp = stack.pop() + tmp
      }
      // 获取重复次数
      stack.push(tmp.repeat(stack.pop()))
      index++
    }
  }
  return stack.join('')
};

• 时间复杂度 O(n)
• 空间复杂度 O(n)