1、 字符串解码
给定一个经过编码的字符串，返回它解码后的字符串。
编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。
示例 1：
输入：s = "3[a]2[bc]"
输出："aaabcbc"
示例 2：
输入：s = "3[a2[c]]"
输出："accaccacc"
递归法
总体思路与辅助栈法一致，不同点在于将 [ 和 ] 分别作为递归的开启与终止条件：
当 s[i] == ']' 时，返回当前括号内记录的 res 字符串与 ] 的索引 i （更新上层递归指针位置）；
当 s[i] == '[' 时，开启新一层递归，记录此 [...] 内字符串 tmp 和递归后的最新索引 i，并执行 res + multi * tmp 拼接字符串。
遍历完毕后返回 res。
复杂度分析：
时间复杂度 O(N)，递归会更新索引，因此实际上还是一次遍历 s；
空间复杂度 O(N)，极端情况下递归深度将会达到线性级别。
class Solution {
public String decodeString(String s) {
return dfs(s, 0)[0];
}
private String[] dfs(String s, int i) {
StringBuilder res = new StringBuilder();
int multi = 0;
while(i < s.length()) {
if(s.charAt(i) >= '0' && s.charAt(i) <= '9')
multi = multi * 10 + Integer.parseInt(String.valueOf(s.charAt(i)));
else if(s.charAt(i) == '[') {
String[] tmp = dfs(s, i + 1);
i = Integer.parseInt(tmp[0]);
while(multi > 0) {
res.append(tmp[1]);
multi--;
}
}
else if(s.charAt(i) == ']')
return new String[] { String.valueOf(i), res.toString() };
else
res.append(String.valueOf(s.charAt(i)));
i++;
}
return new String[] { res.toString() };
}
}