题目：给定一个经过编码的字符串，返回它解码后的字符串。
编码规则为: 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”

    解法1：双栈，时间复杂度o(n)，空间复杂度o(n)

  1. 由于存在括号计算的问题（需要提前计算括号内的结果），因此采用栈的方式更好，又因为需要考虑数字和字母两种不同的元素，因此采用两个栈，一个为字符串栈，一个为数字栈
  2. 遍历原字符串，在遍历规则如下：
    1. 如果是字母，则加入到一个StringBuilder res中，（可能出现aaa3[bc]，因此字母需要提前存入）；
    2. 如果是数字，获取其中的值，num = num * 10 + (str[i] - ‘0’)；
    3. 如果是左括号，此时证明本次运算即将开始，将num和res入栈，且将它们清空用于下次计数
    4. 如果是右括号，说明已经可以结束本次运算了，取出数字栈顶元素，取出字符串栈顶元素tmp_str，且在这个过程中[]内的字符串已经记录在res中了，因此先在for循环中添加数字栈顶元素个次数的res的副本tmp，再让res = new StringBuilder(tmp_str + tmp)
  3. 返回res.toString(); ```java class Solution { public String decodeString(String s) {
    1.  if(s.isEmpty())
    2.      return "";
    3.  Deque<String> deque_str = new LinkedList<>();
    4.  Deque<Integer> deque_num = new LinkedList<>();
    5.  char []str = s.toCharArray();
    6.  int num = 0;
    7.  StringBuilder res = new StringBuilder();
    8.  for(int i = 0 ; i < str.length ; i++){
    9.      if(str[i] >= '0' && str[i] <= '9'){
    10.          num = num * 10 + (str[i] - '0');
    11.      }else if(str[i] == '['){
    12.          deque_num.push(num);
    13.          deque_str.push(res.toString());
    14.          num = 0;
    15.          res = new StringBuilder();
    16.      }else if(str[i] == ']'){
    17.          int count = deque_num.pop();
    18.          StringBuilder tmp = new StringBuilder();
    19.          for(int j = 0 ; j < count ; j++)
    20.              tmp.append(res);
    21.          res = new StringBuilder(deque_str.pop() + tmp);
    22.      }else{
    23.          res.append(str[i]);
    24.      }
    25.  }
    26.  return res.toString();
    }

} ```