394.字符串解码

链接：394.字符串解码
难度：Medium
标签：栈、递归、字符串
简介：给定一个经过编码的字符串，返回它解码后的字符串。

题解 1 - typescript

• 编辑时间：2020-05-28
• 执行用时：64ms
• 内存消耗：32.3MB
• 编程语言：typescript
• 解法介绍：判断是数字还是字母还是[]符号，然后递归遍历。

const numReg = /\d/;
const charReg = /[a-zA-Z]{1}/;
var decodeString = function (s: string): string {
  let res = '';
  let numCache = '';
  for (let i = 0, len = s.length; i < len; i++) {
    const c = s[i];
    if (charReg.test(c)) {
      res += c;
    } else if (numReg.test(c)) {
      numCache += c;
    } else if (c === '[') {
      let count = 1;
      let lastIndex = i;
      while (count !== 0 && lastIndex < len) {
        lastIndex++;
        if (s[lastIndex] === '[') count++;
        if (s[lastIndex] === ']') count--;
      }
      const inS = decodeString(s.substring(i + 1, lastIndex));
      i = lastIndex;
      let insert = '';
      for (let j = 0; j < +numCache; j++) insert += inS;
      res += insert;
      numCache = '';
    }
  }
  return res;
};

题解 2 - typescript

• 编辑时间：2021-05-07
• 执行用时：132ms
• 内存消耗：39.3MB
• 编程语言：typescript
• 解法介绍：栈储存。

function decodeString(s: string): string {
  const numReg = /\d/;
  const stack: string[] = [];
  for (const c of s) {
    if (c === ']') {
      let str = '';
      while (stack[stack.length - 1] !== '[') str = stack.pop()! + str;
      stack.pop();
      let numStr = '';
      while (stack.length !== 0 && numReg.test(stack[stack.length - 1]))
        numStr = stack.pop() + numStr;
      str = str.repeat(+numStr);
      stack.push(str);
    } else {
      stack.push(c);
    }
  }
  return stack.join('');
}