1. 题目描述

给定一个经过编码的字符串，返回它解码后的字符串。
编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。

示例 1：

  1. 输入：s = "3[a]2[bc]"
  2. 输出："aaabcbc"

示例 2：

  1. 输入：s = "3[a2[c]]"
  2. 输出："accaccacc"

示例 3：

  1. 输入：s = "2[abc]3[cd]ef"
  2. 输出："abcabccdcdcdef"

示例 4：

  1. 输入：s = "abc3[cd]xyz"
  2. 输出："abccdcdcdxyz"

2. 解题思路

对于这道题，因为中间涉及到了嵌套的问题，所以我们可以考虑使用栈来解决。

初始化两个栈分别来保存需要重复的字符串和需要重复的次数。那么关键的问题就在于什么时候出入栈了。

入栈时机：遇到[。外部的数字和字母，先去栈里等。

  • 当遇到[，已经扫描的数字就是“倍数”的身份，入栈暂存
  • 当遇到[，已经扫描的字母也要入栈等待，括号里的解码完了，一起参与构建字符串。

出栈时机：遇到]。内层的扫描完了，栈顶元素可以出栈了，共同参与子串的构建。

  • 栈顶就是最近遇到的“倍数”和字母

复杂度分析：

  • 时间复杂度：O(n)，我们需要遍历这个字符串；

  • 空闲复杂度：O(n)，我们需要一个栈来保存需要重复的字符串以及次数，所以在最差的情况下，栈的的长度约等于字符串的长度。

    3. 代码实现

    1. /**
    2. * @param {string} s
    3. * @return {string}
    4. */
    5. var decodeString = function(s) {
    6.   let numStack = []
    7.   let strStack = []
    8.   let num = 0
    9.   let res = ""
    11.   for(let item of s){
    12.       if(!isNaN(item)){
    13.           num = num * 10 + Number(item)
    14.       }else if(item === "["){
    15.           strStack.push(res)
    16.           res = ""
    17.           numStack.push(num)
    18.           num = 0
    19.       }else if(item === "]"){
    20.           res = strStack.pop() + res.repeat(numStack.pop())
    21.       }else{
    22.           res += item
    23.       }
    24.   }
    25.   return res
    26. };

    4. 提交结果

    image.png