问题描述
LeetCode 394. 字符串解码 (opens in a new tab)，难度中等。
给定一个经过编码的字符串，返回它解码后的字符串。
编码规则为: 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 <= s.length <= 30s由小写英文字母、数字和方括号'[]'组成s保证是一个 有效 的输入。s中所有整数的取值范围为[1, 300]
题解
题解：利用 stack 的特点实现，类似20. 有效的括号 (opens in a new tab)等题目。
Solution.java
class Solution {
public String decodeString(String s) {
// 用于处理嵌套 []，例如：3[a2[c]]
int lock = 0;
StringBuffer ans = new StringBuffer();
Stack<Character> stack = new Stack<>();
for (int i = 0; i < s.length(); ++i) {
if (s.charAt(i) == ']') {
// 如果是 ]
// 取出 [] 之间的字符串
StringBuffer sb = new StringBuffer();
while (!stack.isEmpty() && stack.peek() != '[') {
sb.append(stack.pop());
}
stack.pop(); // 去掉 [
sb.reverse(); // 字符串反转
// 获取 n，n 的范围 [0, 300]
int n = 0;
int level = 1; // n 可能大于 9
while (!stack.isEmpty() && stack.peek() >= '0' && stack.peek() <= '9') {
n += (stack.pop() - '0') * level;
level *= 10;
}
// 还原加密的字符串
StringBuffer temp = new StringBuffer();
while (n-- > 0) {
temp.append(sb);
}
if (--lock > 0) { // 判断是不是嵌套 []
// 如果是嵌套 []，将字符串压入 stack 中
for (int k = 0; k < temp.length(); k++) {
stack.push(temp.charAt(k));
}
} else {
// 不是嵌套
ans.append(temp);
}
} else if (s.charAt(i) == '[' || (s.charAt(i) >= '0' && s.charAt(i) <= '9') || (s.charAt(i) >= 'a' && s.charAt(i) <= 'z' && lock > 0)) {
// 需要将解密的字符都压入 stack 中，比如 2[c]
stack.push(s.charAt(i));
if (s.charAt(i) == '[') {
lock++;
}
} else {
ans.append(s.charAt(i));
}
}
return ans.toString();
}
}