21-05-26-2-字符串解码

题目地址

https://leetcode-cn.com/problems/decode-string/

题目描述

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

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

前置知识

栈和括号匹配。

思路

• 遍历字符串，检测不同的字符做不同的处理。
• 遇到数字就累加变量multi。
• 遇到字母就累加临时变量，即拼接字符串res。
• 遇到[就将当时的临时结果res和multi压入栈，方便下次弹出计算结果。然后清空res和置0multi。
• 当遇到]，利用栈FIFO的特性做[]匹配，就弹出栈顶上一个[产生的临时结果，假设为prev和prevMulti，然后进行prev + prevMulti * res的运算，再清空multi，因为最后一个字符一定是]，所以此时不用清空res。
• 最后遍历完，返回res。

代码

/**
 * @param {string} s
 * @return {string}
 */
var decodeString = function (s) {
  let res = '';
  let multi = 0;
  const stack = [];
  const length = s.length;
  for (let i = 0; i < length; i ++) {
    if (s[i] === '[') {
      // 将当前临时结果入栈
      stack.push([multi, res]);
      res = '';
      multi = 0;
    } else if (s[i] === ']') {
      // 出栈计算结果
      let temp = '';
      const pop = stack.pop();
      for (let i = 0; i < pop[0]; i ++) {
        temp += res;
      }
      res = pop[1] + temp;
      multi = 0;
    } else if (isNaN(Number(s[i]))) {
      // 字母累加结果
      res += s[i];
    } else {
      // 数字叠加，注意连续数字的进制运算
      // 例如100[xxx]
      multi = multi * 10 + Number(s[i]);
    }
  }
  return res;
};

复杂度分析

• 时间复杂度：O(N)
• 空间复杂度：O(N)