这道题主要涉及的是对递归和栈的理解。
原题
给定一个经过编码的字符串，返回它解码后的字符串。
编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。
示例:
s = "3[a]2[bc]", 返回 "aaabcbc".
s = "3[a2[c]]", 返回 "accaccacc".
s = "2[abc]3[cd]ef", 返回 "abcabccdcdcdef".
解题
递归
这道题目，简单来看就是根据数字和内容，进行不断重复输出，最终得出结果。因此，递归也是最容易让人想到的。
数字代表内容需要重复的次数，[代表一次新的递归开始，]代表本次递归的结束，有点类似括号匹配这种问题。只是需要记录中间结果，以及最开始的s进过一次递归遍历后的下标位置。
基于上面的讲解，我们也就能够写出代码：
class Solution {
public String decodeString(String s) {
StringBuilder resultSb = new StringBuilder();
dfs(s, 0, resultSb);
return resultSb.toString();
}
public int dfs(String s, int index, StringBuilder resultSb) {
// 需要重复的次数
int count = 0;
while (index < s.length()) {
char temp = s.charAt(index);
// 如果是数字，则先累计进count中
if (temp >= '0' && temp <= '9') {
count = count * 10 + temp - '0';
}
// 遇到'['，则开始新一轮的递归
else if (temp == '[') {
StringBuilder tempResult = new StringBuilder();
index = dfs(s, index + 1, tempResult);
// 重复
for (int i = 0; i < count; i++) {
resultSb.append(tempResult);
}
// count进行重置
count = 0;
}
// 遇到']'，结束递归
else if (temp == ']') {
// 返回新的下标
return index;
}
// 遇到字母
else {
resultSb.append(temp);
}
index++;
}
return index;
}
}
提交OK。
利用栈
既然有递归的写法，那么自然有不递归的写法，这就需要借助栈了。大家可以类比成计算一段普通的数学表达式，里面有括号、数字、符号运算等，所以需要两个栈，分别存储数字和运算符。
这道题目自然也是需要两个栈的，一个用来存储重复的次数，一个用来存储中间的字符串结果。判断出栈、入栈的依据，依据是[]，[代表数字和字符串都压入相应的栈，]代表需要将数字和字符串都需要从栈首压出，进行计算。
接下来看看代码：
class Solution {
public String decodeString(String s) {
// 存放次数的栈
Stack<Integer> countStack = new Stack<>();
// 存放字符串的栈
Stack<StringBuilder> sbStack = new Stack<>();
// 临时存储字符串的内容
StringBuilder tempSb = new StringBuilder();
// 临时存储数字的内容
int tempCount = 0;
// 遍历
for(char temp : s.toCharArray()) {
// 如果是数字，则先累计进tempCount中
if (temp >= '0' && temp <= '9') {
tempCount = tempCount * 10 + temp - '0';
}
// 遇到'['，将之前的数字和字符串放进countStack中
else if (temp == '[') {
countStack.push(tempCount);
tempCount = 0;
sbStack.push(tempSb);
tempSb = new StringBuilder();
}
// 遇到']'，从countStack拿出数字
else if (temp == ']') {
// 重复
StringBuilder tempResult = new StringBuilder();
int count = countStack.pop();
for (int j = 0; j < count; j++) {
tempResult.append(tempSb);
}
// 拿出sbStack第一个
StringBuilder sb = sbStack.pop();
tempSb = sb.append(tempResult);
}
// 遇到字母
else {
tempSb.append(temp);
}
}
return tempSb.toString();
}
}
提交OK。
总结
以上就是这道题目我的解答过程了，不知道大家是否理解了。这道题主要涉及的是对递归和栈的理解，有点类似数学表达式的计算，只是做一下类比即可。
有兴趣的话可以访问我的博客或者关注我的公众号、头条号，说不定会有意外的惊喜。
公众号：健程之道