题目描述
给定一个经过编码的字符串，返回它解码后的字符串。
编码规则为: 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"
解题思路一：栈
本题中可能出现括号嵌套的情况一般考虑用栈来实现，比如 2[a2[bc]]，这种情况下我们可以先转化成 2[abcbc]，在转化成 abcbcabcbc。具体的做法如下：
- 如果当前的字符为数位，解析出一个数字（连续的多个数位）并进栈
- 如果当前的字符为字母或者左括号，直接进栈
- 如果当前的字符为右括号，开始出栈，一直到左括号出栈，出栈序列反转后拼接成一个字符串，此时取出栈顶的数字（此时栈顶一定是数字，想想为什么？），就是这个字符串应该出现的次数，我们根据这个次数和字符串构造出新的字符串并进栈
重复如上操作，最终将栈中的元素按照从栈底到栈顶的顺序拼接起来，就得到了答案
代码如下：
class Solution {
int ptr;
public String decodeString(String s) {
LinkedList<String> stk = new LinkedList<String>();
ptr = 0;
while (ptr < s.length()) {
char cur = s.charAt(ptr);
if (Character.isDigit(cur)) {
// 获取一个数字并进栈
String digits = getDigits(s);
stk.addLast(digits);
} else if (Character.isLetter(cur) || cur == '[') {
// 获取一个字母并进栈
stk.addLast(String.valueOf(s.charAt(ptr++)));
} else {
++ptr;
LinkedList<String> sub = new LinkedList<String>();
while (!"[".equals(stk.peekLast())) {
sub.addLast(stk.removeLast());
}
Collections.reverse(sub);
// 左括号出栈
stk.removeLast();
// 此时栈顶为当前 sub 对应的字符串应该出现的次数
int repTime = Integer.parseInt(stk.removeLast());
StringBuffer t = new StringBuffer();
String o = getString(sub);
// 构造字符串
while (repTime-- > 0) {
t.append(o);
}
// 将构造好的字符串入栈
stk.addLast(t.toString());
}
}
return getString(stk);
}
public String getDigits(String s) {
StringBuffer ret = new StringBuffer();
while (Character.isDigit(s.charAt(ptr))) {
ret.append(s.charAt(ptr++));
}
return ret.toString();
}
public String getString(LinkedList<String> v) {
StringBuffer ret = new StringBuffer();
for (String s : v) {
ret.append(s);
}
return ret.toString();
}
}解题思路二：递归
每一层递归返回一个数组：1展开所有中括号内的字符后i的下标，2根据数字拼接中括号内字符的"最终结果"
具体步骤如下：
当 s[i] == ']' 时，返回当前括号内记录的 res 字符串与 ] 的索引 i （更新上层递归指针位置）；
当 s[i] == '[' 时，开启新一层递归，记录此 [...] 内字符串 tmp 和递归后的最新索引 i，并执行 res + multi * tmp 拼接字符串。
遍历完毕后返回 res。
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
i = Integer.parseInt(tmp[0]);
while(multi > 0) {
res.append(tmp[1]);
multi--;
}
}
else if(s.charAt(i) == ']')
//返回"]" 的索引 i与 res 字符串
return new String[] { String.valueOf(i), res.toString() };
else
res.append(String.valueOf(s.charAt(i)));
i++;
}
//s中括号内的字符由上一个return返回,这个return返回中括号以后剩余的字符拼接的结果
return new String[] { res.toString() };
}
}