【Day 4 】2024-04-11 - 394. 字符串解码

[azl397985856]

394. 字符串解码

入选理由

暂无

题目地址

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"

[atom-set]

思路

• 可以理解为括号匹配的升级版
• 遍历字符串，借助数组存放过程态
• 逆向遍历字符串，寻找 [ ] 之间包裹的字符串
• 继续往前寻找数字，遇到字符结束

代码

/**
 * @param {string} s
 * @return {string}
 */
var decodeString = function (s) {
  var num = [];
  var stack = [];
  var len = String(s).length;
  // 标识是否遇到
  var flag = 0;

  for (var p = len - 1; p >= 0; p--) {
    var ch = s.charAt(p);
    // 非数字进入
    if (isNaN(Number(ch))) {
      if (flag === 0) {
        stack.push(ch);
        continue;
      }

      // 数字
      var k = Number(num.join(""));
      var stop = false;
      var sub = [];
      // console.log("k:", stack, k);

      while (!stop) {
        var t = stack.pop();
        if (t === "[") {
          continue;
        }
        if (t === "]") {
          // 重复 k 次
          for (var n = 0; n < k; n++) {
            stack.push(sub.join(""));
          }
          stop = true;
          continue;
        } else {
          sub.push(t);
        }
      }
      stack.push(ch);
      // console.log("step:", stack, p);
      flag = 0;
      num = [];
      sub = [];
      continue;
    } else {
      num.unshift(ch);
      flag = 1;
    }
  }

  // console.log("step:", stack, num);
  if (num.length > 0) {
    var k = Number(num.join(""));
    var stop = false;
    var sub = [];
    while (!stop) {
      var t = stack.pop();
      if (t === "[") {
        continue;
      }
      if (t === "]") {
        // 重复 k 次
        // console.log("sub:", sub, k);
        for (var n = 0; n < k; n++) {
          stack.push(sub.join(""));
        }
        stop = true;
        break;
      }
      sub.push(t);
    }
  }

  return stack.reverse().join("");
};

复杂度分析

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

[zhiyuanpeng]

class Solution:
    def decodeString(self, s: str) -> str:
        stack = []
        for c in s:
            if c == "]":
                rep = []
                while True:
                    top = stack.pop()
                    if top == "[":
                        k = []
                        while stack and stack[-1] in "0123456789":
                            k.append(stack.pop())
                        k = int("".join(k[::-1]))
                        for i in range(k):
                            stack += rep[::-1]
                        break
                    else:
                        rep.append(top)
            else:
                stack.append(c)
        return "".join(stack)

time N space N where N is the len(decoded s)

[hillsonziqiu]

思路

这类字符串匹配括号或者特殊符号的场景，我一般首先想到的要不就是用字符串替换法（正则），要不就用栈来操作。本题题解就用栈的形式进行操作： 针对字符串做一次遍历，遍历过程中要处理几个条件： 统一点，除了']'和数字类型需要单独处理外，将其余的char统统推入栈中；

1. '!isNaN(char)' 用于计算重复次数，之前以为数字只会是1位，导致用例 100[leetcode] 没过。 在一次遍历中只能获取一位数字，那么在遇到'['之前数字是要累加的，算法为：times = times * 10 + parseInt(item);
2. '[' 将之前算好的次数推入栈中。并将全局变量times重置为0；
3. ']'
   • 这里是重点 *，首先这里是要计算需要重复字符串的，循环从已有的stack中pop元素，当遇到'['需要停止，并再次pop出来之前计算的重复次数times，然后将+=后的repeatStr推入栈中
4. 其他 当前char 统统推入栈中

通过这次遍历，那么整个栈都只剩下string[] 了。然后将字符串数组拼接起来，就是最终的答案了。

解法

var decodeString = function (s) {
  const stack = [];
  let times = 0;
  // 考虑栈的操作
  for (const item of s) {
    if (item === "[") {
      stack.push(times);
      stack.push(item);
      times = 0;
    } else if (item === "]") {
      let repeatStr = "";
      while (1) {
        const stackPopItem = stack.pop();
        if (stackPopItem === "[") {
          const repeatTimes = stack.pop();
          repeatStr = repeatStr.repeat(repeatTimes);
          break;
        } else {
          repeatStr = stackPopItem + repeatStr;
        }
      }
      stack.push(repeatStr);
    } else if (!isNaN(item)) {
      times = times * 10 + parseInt(item);
    } else {
      stack.push(item);
    }
  }

  console.log("res", stack);
  return stack.join("");
};

复杂度分析

时间复杂度：for 循环里包含了一个while循环 我感觉复杂度是 O(n^2) 然后还有个join 那么总时间复杂度应该是 O(n^2 + n); 按算法来看时间复杂度应该是O(n^2); 空间复杂度：此处用了一个位数为n的栈，故空间复杂度为O(n) 。

[hillsonziqiu]

思路

这类字符串匹配括号或者特殊符号的场景，我一般首先想到的要不就是用字符串替换法（正则），要不就用栈来操作。本题题解就用栈的形式进行操作： 针对字符串做一次遍历，遍历过程中要处理几个条件： 统一点，除了']'和数字类型需要单独处理外，将其余的char统统推入栈中；

1. '!isNaN(char)' 用于计算重复次数，之前以为数字只会是1位，导致用例 100[leetcode] 没过。 在一次遍历中只能获取一位数字，那么在遇到'['之前数字是要累加的，算法为：times = times * 10 + parseInt(item);
2. '[' 将之前算好的次数推入栈中。并将全局变量times重置为0；
3. ']'

• 这里是重点 *，首先这里是要计算需要重复字符串的，循环从已有的stack中pop元素，当遇到'['需要停止，并再次pop出来之前计算的重复次数times，然后将+=后的repeatStr推入栈中

4. 其他 当前char 统统推入栈中

通过这次遍历，那么整个栈都只剩下string[] 了。然后将字符串数组拼接起来，就是最终的答案了。

解法

var decodeString = function (s) {
  const stack = [];
  let times = 0;
  // 考虑栈的操作
  for (const item of s) {
    if (item === "[") {
      stack.push(times);
      stack.push(item);
      times = 0;
    } else if (item === "]") {
      let repeatStr = "";
      while (1) {
        const stackPopItem = stack.pop();
        if (stackPopItem === "[") {
          const repeatTimes = stack.pop();
          repeatStr = repeatStr.repeat(repeatTimes);
          break;
        } else {
          repeatStr = stackPopItem + repeatStr;
        }
      }
      stack.push(repeatStr);
    } else if (!isNaN(item)) {
      times = times * 10 + parseInt(item);
    } else {
      stack.push(item);
    }
  }

  console.log("res", stack);
  return stack.join("");
};

复杂度分析

时间复杂度：for 循环里包含了一个while循环 我感觉复杂度是 O(n^2) 然后还有个join 那么总时间复杂度应该是 O(n^2 + n); 按算法来看时间复杂度应该是O(n^2); 空间复杂度：此处用了一个位数为n的栈，故空间复杂度为O(n) 。

又来纠错了，时间复杂度：for循环 O(n), 内层while循环也是O(n), 还有个join方法复杂度也是O(n) 那么sum后复杂度为O(3n);按照算法来看时间复杂度应为O(n);

[wwz223]

思路

定义了三个栈空间，分别存放返回数据、循环次数数组、left坐标数组，通过同步进栈出栈保持同步

答案

/**
 * @param {string} s
 * @return {string}
 */
var decodeString = function (s) {
  let stack = [];
  let numsStack = [];
  let leftStack = [];
  let num = 0;
  let left = 0;
  for (let i = 0; i < s.length; i++) {
    k = s[i];
    if (k === '[') {
      numsStack.push(num);
      leftStack.push(i);
      num = 0;
    } else if (k === ']') {
      num = numsStack.pop();
      left = leftStack.pop();

      num--;
      if (num > 0) {
        i = left - 1;
      }
    } else if (!isNaN(Number(k))) {
      num = num > 0 ? num * 10 + Number(k) : Number(k);
    } else {
      num = 0;
      stack.push(k);
    }
  }
  return stack.join('');
};

复杂度分析 O(n2)

空间复杂度 O(n)

[jinzhepro]

思路

使用栈结构，存放string和num，然后匹配]依次推出

/**
 * @param {string} s
 * @return {string}
 */
var decodeString = function(s) {
  var stack = []
  var string = ''
  var num = 0
  for (var i = 0; i < s.length; i++) {
    if(!isNaN(s[i])) {
      num = num * 10 + Number(s[i])
    }else if(s[i] === '[') {
      stack.push([string, num])
      string = ''
      num = 0
    }else if(s[i] === ']'){
      const val = stack.pop()
      string = val[0] + string.repeat(val[1])
    }else{
      string += s[i]
    }
  }
  console.log(string)
  return string
};

复杂度

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

[xil324]

/**
 * @param {string} s
 * @return {string}
 */
var decodeString = function(s) {
    const stack = []; 
    for(const char of s) {
        if(char !== ']') {
            stack.push(char); 
            continue; 
        } 
        let arr = []; 
        while(stack.length && stack[stack.length-1] !== '['){
            arr.unshift(stack.pop())
        }
        stack.pop(); 
        const str = arr.join(""); 

        let repeatNumberArr = []
        while(!Number.isNaN(Number(stack[stack.length-1]))) {
            repeatNumberArr.unshift(stack.pop())
        }
        stack.push(str.repeat(Number(repeatNumberArr.join(""))))
    }
    return stack.join("")
};

time complexity: O(n) where n is the length of the string space complexity: O(n)

[Martina001]

思路： 上来第一眼就知道可以用递归或者栈（记不住正则表达式的匹配，没考虑这个解法），用栈更直观一点，但是出错了几次，备注一下，重点在以下几点因素需要考虑： // 1.每个[]中的字符串都要处理完之后重新入栈 // 2。本以为要对每段开头和结尾独立的字母序列特殊处理，但其实当执行完上一步之后，直接把栈中所有字母加入结果集即可 // 3。 注意[左边的数字可能不止一位 // 4。由于步骤1中重新入栈的操作，所以一次性入栈String比一个个再入栈字符更好，故Stack中存储String而不是Character

private String decodeString1(String s) { LinkedList stack = new LinkedList<>(); int i = 0; int n = s.length(); while (i < n) { char c = s.charAt(i); if (Character.isLetter(c) || c == '[') { stack.addLast(String.valueOf(c)); i++; } else if (Character.isDigit(c)) { // 提前处理数字 StringBuffer sbDigit = new StringBuffer(); while (Character.isDigit(s.charAt(i))) { sbDigit.append(s.charAt(i++)); } stack.addLast(sbDigit.toString()); } // 遇到了']' 重新处理后入栈 else { i++; LinkedList sb = new LinkedList(); while (!"[".equals(stack.peekLast())) { sb.addFirst(stack.removeLast()); } stack.removeLast(); int num = Integer.parseInt(stack.removeLast()); String ssb = getString(sb); StringBuffer str = new StringBuffer(); while(num-->0){ str.append(ssb); } stack.addLast(str.toString()); } } return getString(stack); }

    public String getString(LinkedList<String> v) {
        StringBuffer res = new StringBuffer();
        for (String s : v) {
            res.append(s);
        }
        return res.toString();
    }

空间复杂度很明显，用到了栈，是O(n) 时间复杂度有点不太确定，直觉告诉我是O(n)，但是感觉中括号内的字符串会被循环多次（入栈出栈），求问为何这些不会被算入时间复杂度

[Martina001]

@hillsonziqiu

思路

这类字符串匹配括号或者特殊符号的场景，我一般首先想到的要不就是用字符串替换法（正则），要不就用栈来操作。本题题解就用栈的形式进行操作： 针对字符串做一次遍历，遍历过程中要处理几个条件： 统一点，除了']'和数字类型需要单独处理外，将其余的char统统推入栈中；

1. '!isNaN(char)' 用于计算重复次数，之前以为数字只会是1位，导致用例 100[leetcode] 没过。 在一次遍历中只能获取一位数字，那么在遇到'['之前数字是要累加的，算法为：times = times * 10 + parseInt(item);
2. '[' 将之前算好的次数推入栈中。并将全局变量times重置为0；
3. ']'

• 这里是重点 *，首先这里是要计算需要重复字符串的，循环从已有的stack中pop元素，当遇到'['需要停止，并再次pop出来之前计算的重复次数times，然后将+=后的repeatStr推入栈中

4. 其他 当前char 统统推入栈中

通过这次遍历，那么整个栈都只剩下string[] 了。然后将字符串数组拼接起来，就是最终的答案了。

解法

var decodeString = function (s) {
  const stack = [];
  let times = 0;
  // 考虑栈的操作
  for (const item of s) {
    if (item === "[") {
      stack.push(times);
      stack.push(item);
      times = 0;
    } else if (item === "]") {
      let repeatStr = "";
      while (1) {
        const stackPopItem = stack.pop();
        if (stackPopItem === "[") {
          const repeatTimes = stack.pop();
          repeatStr = repeatStr.repeat(repeatTimes);
          break;
        } else {
          repeatStr = stackPopItem + repeatStr;
        }
      }
      stack.push(repeatStr);
    } else if (!isNaN(item)) {
      times = times * 10 + parseInt(item);
    } else {
      stack.push(item);
    }
  }

  console.log("res", stack);
  return stack.join("");
};

复杂度分析

时间复杂度：for 循环里包含了一个while循环 我感觉复杂度是 O(n^2) 然后还有个join 那么总时间复杂度应该是 O(n^2 + n); 按算法来看时间复杂度应该是O(n^2); 空间复杂度：此处用了一个位数为n的栈，故空间复杂度为O(n) 。

又来纠错了，时间复杂度：for循环 O(n), 内层while循环也是O(n), 还有个join方法复杂度也是O(n) 那么sum后复杂度为O(3n);按照算法来看时间复杂度应为O(n);

求问，为啥这里是3n 不是n^ 3呢

[Dtjk]

class Solution {
public:
    string decodeString(string s) {
    stack<int> numStack;
    stack<string> resStack;
    int num = 0;
    string res;
    for (int i = 0; i < s.size(); i++) {
        if (isalpha(s[i])) {
            res.push_back(s[i]);
        } else if (isdigit(s[i])) {
            num = num * 10 + s[i] - '0';
        } else if (s[i] == '[') {
            resStack.push(res);
            res = "";
            numStack.push(num);
            num = 0;
        } else {
            for (int j = 0; j < numStack.top(); j++) {
                resStack.top() += res;
            }
            numStack.pop();
            res = resStack.top();
            resStack.pop();
        }
    }
    return res;
}
};

[smallppgirl]

思路： stack 代码：

class Solution:
    def decodeString(self, s: str) -> str:
        stack = []
        res = ""
        mul = 0
        for ch in s:
            if ch == "[":
                stack.append((mul, res))
                res, mul = "", 0
            elif ch == "]":
                cur_mul, last_res = stack.pop()
                res = last_res + cur_mul * res
            elif "0" <= ch <= "9":
                mul = mul * 10 + int(ch)
            else:
                res += ch
        return res

时间 ：O(n) 空间： O(n)

[CathyShang]

思路

• 用栈维护，记录字符型数字 与 字符串
• 当遇到“[” 入栈; 当遇到“]” 出栈。

代码

class Solution {
public:
    string decodeString(string s) {
        // 解码   没跑通
        stack<string> stkStr;
        // stack<int> stkNum;
        int n = s.size(), num;
        string temp1,temp2,sNum;
        string res;
        int flag = -1, k=1;
        string q; 
        // 
        for(int i=0; i<n; i++){
            if(s[i]>='a' && s[i]<='z'){
                temp1 += s[i];
            }
            else{sNum += s[i];}
            if(s[i]=='['){
                flag = 1;
                if(sNum==''){sNum = "1";} // 错误
                // else{num = stoi(sNum)}                
                if(temp1!=''){stkStr.push(temp1);}
                stkStr.push(num);
                stkStr.push(s[i]);
                // 入栈后清零
                temp1 = '';
                sNum = '';
            }
            if(s[i]==']'){
                //出栈
                q = stkStr.pop();
                if(q=='['){
                    k = stkStr.pop()
                    k = stoi(k);
                    for(int j =0; j<k; i++){
                        temp2 += temp1;
                    }
                }
                else{
                    temp2 = stkStr.pop() + temp2;
                    stkStr.pop()
                }
            }
        }
        k = stkStr.pop()
        k = stoi(k);
        for(int j =0; j<k; i++){
            res += temp2;
            }        
        if(!flag){return temp1;}
        else{
            if(temp1!=''){
                res += temp1;
            }
            return res;}
    }
};

复杂度

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

[GReyQT]

题解思路：

（1）从字符头开始处理，采用栈存储，先进先出，使得当前的最内层的括号优先处理； 代码：

class Solution {
public:
string decodeString(string s) {
        stack<char> strstack;
        string res;
        for (int i = 0; i < s.size(); ++i)
        {
            if (s[i] != ']')
            {
                strstack.push(s[i]);//字符逐个压栈
            }
            else
            {
                string temp;
                while (strstack.top() != '[')//获取重复的字符串
                {
                    temp = strstack.top() + temp;
                    strstack.pop();
                }
                strstack.pop();//[出栈
                string numstr;
                while (!strstack.empty() && isdigit(strstack.top()))//获取重复字符出重复的次数
                {
                    numstr = strstack.top() + numstr;
                    strstack.pop();
                }
                int count = stoi(numstr);
                string countstr;
                while (count--)//获取完整的重复字符串
                {
                    countstr += temp;
                }
                for (int j = 0; j < countstr.size(); ++j)//将完整的重复字符串压栈
                {
                    strstack.push(countstr[j]);
                }
            }
        }
        // 将栈中元素连接成字符串
        while (!strstack.empty()) {
            res += strstack.top();
            strstack.pop();
        }
        // 反转字符串，因为栈是后进先出的
        reverse(res.begin(), res.end());
        return res;
    }
};

复杂度分析：

• 时间复杂度：取决于字符串s的长度n，因此时间复杂度为O(n)
• 空间复杂度：额外使用栈空间存储字符串， 且使用的栈空间大小取决于字符串s中'['的个数，因此最坏的空间复杂度为O(n/2)，因此空间复杂度为O(n)

[Hawkins-hjq]

思路

双栈

代码

class Solution {
    public String decodeString(String s) {
        Deque<StringBuilder> stack = new LinkedList<>();
        Deque<Integer> numStack = new LinkedList<>();
        StringBuilder sb = new StringBuilder();
        int num = 0;
        for (int i = 0; i < s.length(); i++) {
            if (Character.isDigit(s.charAt(i))) {
                num = num * 10 + s.charAt(i) - '0';
            } else if (s.charAt(i) == '[') {
                numStack.push(num);
                num = 0;
                stack.push(sb);
                sb = new StringBuilder();
            } else if (Character.isLetter(s.charAt(i))) {
                sb.append(s.charAt(i));
            } else {
                StringBuilder temp = stack.pop();
                int count = numStack.pop();
                for (int j = 0; j < count; j++) {
                    temp.append(sb);
                }
                sb = temp;
            }
        }
        return sb.toString();

    }
}

复杂度

时间复杂度：O（N） 空间复杂度：O（N）

[coderXiaowq]

Java 昨天写的时候思路有,但是代码实现总是差一点,最后虽然实现了,觉有运气的成分,心烦 时间复杂度O(n)

class Solution {
    public String decodeString(String s) {
        StringBuilder rs = new StringBuilder();
        Stack<Integer> nums = new Stack<>();
        Stack<String> chs = new Stack<>();
        int num = 0;
        char[] a = s.toCharArray();
        for (char c : a) {
            if (c >= '0' && c <= '9') {
                num = num * 10 + c - '0';
            } else if (c >= 'a' && c <= 'z' || c >= 'A' && c <= 'Z') {
                rs.append(c);
            } else if (c == '[') {
                nums.push(num);
                chs.push(rs.toString());
                rs = new StringBuilder();//重置rs
                num = 0;
            } else {
                int N = nums.pop();//重复次数N
                String tmp = chs.pop();
                for (int j = 0; j < N; j++) {
                    tmp += rs.toString();
                }
                rs = new StringBuilder(tmp);
            }

        }
        return rs.toString();
    }
}

[YANGLimbo]

看了别人的思路写了双栈版本，语言为c++：

定义和初始化变量：

• countStack：一个整数栈，用于存储每个方括号前的重复次数。
• stringStack：一个字符串栈，用于存储当前正在构建的字符串片段。
• pattern：当前正在构建的字符串。
• time：用于计算方括号前的数字，即重复次数。

  如果当前字符是 ']'，表示一个重复序列的结束：

• 从 countStack 中弹出顶部元素到 repeat，表示需要重复的次数。
• 从 stringStack 中弹出顶部字符串到 last，这是重复内容之前的字符串。

• 将 pattern 重复 repeat 次并追加到 last 后，然后将结果赋值回 pattern。

  如果当前字符是字母，直接追加到 pattern。

  class Solution {
  public:
  string decodeString(string s) {
      std::stack<int> countStack;
      std::stack<string> stringStack;
      string pattern;
      int time = 0;
  
      for(char c : s){
          if(c >= '0' && c <= '9'){
              time = time * 10 + (c-'0');  
          }else if(c == '['){
              // 已确定的字符串入栈
              // 之后重复的次数入栈
              countStack.push(time);
              stringStack.push(pattern);
              pattern.clear(); // 重置
              time = 0;
          }else if(c == ']'){
              int repeat = countStack.top();
              countStack.pop();
              string last = stringStack.top();
              stringStack.pop();
              while(repeat--){
                  last += pattern;
              }
              pattern = last;
          }else{
              // 字母
              pattern += c;
          }
      }
      return pattern;
  }
  };

  旧版（错误版） 写了一个没有用到栈的错误版本，不支持[]的嵌套，而且以字母结尾的情况也不支持。明天再看看提示重写吧。sad

  class Solution {
  public:
  string decodeString(string s) {
      int len = s.size();
      vector<int> repeats;
      vector<string> patterns;
      char c;
      string repeat;
      string pattern;
      string ans;
      for(int i = 0 ; i < len; i++){
          c = s[i];
          if(c >= '0' && c <= '9'){
              // 也有可能是pattern记录结束
              if(!pattern.empty()){
                  repeats.push_back(1);
                  patterns.push_back(pattern);
                  pattern.clear();
              }
              repeat += c;
          }else if(c == '['){
              // 说明repeat记录完毕
              repeats.push_back(stoi(repeat));
              repeat.clear();
          }else if(c == ']'){
              // pattern记录完毕
              patterns.push_back(pattern);
              pattern.clear();
          }else{
              // 记录pattern
              pattern += c;
          }
      }
      for(int i = 0; i < repeats.size(); i++){
          int num = repeats[i];
          printf("%d",num);
          printf("%s\n",patterns[i].c_str());
          for(int j = 0; j < num; j++){
              ans += patterns[i];
          }
      }
      return ans;
  }
  };

[Alexzhang-Mini]

class Solution: def decodeString(self, s: str) -> str: stack = [] current_str = "" repeat_num = 0

    for char in s:
        if char.isdigit():
            repeat_num = repeat_num * 10 + int(char)
        elif char.isalpha():
            current_str += char
        elif char == "[":
            stack.append((current_str, repeat_num))
            current_str = ""
            repeat_num = 0
        elif char == "]":
            last_str, last_repeat = stack.pop()
            current_str = last_str + current_str * last_repeat

    return current_str

[pandapls]

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

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

### 思路

 使用栈

### 代码

```javascript
var decodeString = function(s) {
  let stack = []
  for (const char of s) {
    if (char !== ']') { // ] 前的字符都入栈
      stack.push(char)
      continue
    }
    let cur = stack.pop() // 弹出一个来检测
    let str = '' // 组装字符串
    // 接下来肯定是遇到字母，直到遇到 [
    while (cur !== '[') {
      str = cur + str // cur字符加在左边
      cur = stack.pop() // 再拉出一个
    }
    // 此时cur为 [，接下来要遇到数字
    let num = ''
    cur = stack.pop() // 用下一个将 [ 覆盖
    while (!isNaN(cur)) {
      num = cur + num // 数字字符加在左边
      cur = stack.pop() // 再拉出一个
    }
    // 现在要么是字母，要么是 [
    stack.push(cur)
    stack.push(str.repeat(num))
  }
  return stack.join('')
};

复杂度分析

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