给定一个经过编码的字符串，返回它解码后的字符串。
编码规则为: 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"
本题很容易有一个朴素的想法：递归求解，把[]当作一个整体，进行递归展开
但是在遇到 ] 时，需要分情况处理，如果他是字符串中最后一个，那么不用管，直接返回当前积累的字符串
如果后面还有，那么就需要移动指针
(md题解看到的这个算法太强了，我被震慑了
class Solution {// 从索引为index的字符开始处理// 返回string数组，如果当前已经遍历完字符串s，那么数组元素只有一个：rs字符串// 如果当前遇到]，但还不是最后一个字符，那么还需要返回当前]的index，以便移动指针，处理]之后的private boolean isDigit(String s,int i){return s.charAt(i)>='0'&&s.charAt(i)<='9';}private String[] dfs(String s,int index){StringBuilder sb=new StringBuilder();int mul=0;while(index<s.length()){if(isDigit(s,index)){mul=mul*10+s.charAt(index)-'0';}else if(s.charAt(index)=='['){// 开始递归处理String[] t=dfs(s,index+1);index=Integer.parseInt(t[0]);while(mul>0){sb.append(t[1]);mul--;}}else if(s.charAt(index)==']'){return new String[]{String.valueOf(index),sb.toString()};}else{sb.append(s.charAt(index));}index++;}return new String[]{sb.toString()};}public String decodeString(String s) {return dfs(s,0)[0];}
}换了种做法，还是懵懵的：
class Solution {public String decodeString(String s) {ArrayDeque<Integer> numStack = new ArrayDeque<>();ArrayDeque<String> strStack = new ArrayDeque<>();StringBuilder rs = new StringBuilder();char[] a = s.toCharArray();int curNum = 0;StringBuilder curStr = new StringBuilder();for (int i = 0; i < a.length; i++) {if (a[i] >= '0' && a[i] <= '9') {curNum = curNum * 10 + a[i] - '0';} else if (a[i] == '[') {strStack.push(curStr.toString());curStr = new StringBuilder();// 遇到左括号，数组入栈numStack.push(curNum);curNum = 0;} else if (a[i] == ']') {// 数字出栈，连接curNum = numStack.pop();StringBuilder tsb = new StringBuilder(strStack.pop());while (curNum > 0) {tsb.append(curStr);curNum--;}curStr = tsb;} else {curStr.append(a[i]);}}if (curStr.length() > 0) {rs.append(curStr.toString());}return rs.toString();}
}