欢迎光临小站：致橡树
字符串解码
给定一个经过编码的字符串，返回它解码后的字符串。
编码规则为: 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]
解题思路
栈数据结构
该算法使用栈数据结构来处理嵌套的重复模式，主要思想如下：
遍历字符：逐个处理输入字符串的每个字符。
四种情况处理：
字母字符：直接添加到当前字符串构建器(sb)中。
数字字符：累积计算重复次数(multi)，处理多位数字的情况。
左括号'['：将当前字符串和重复次数压入栈，并重置这些变量。
右括号']'：弹出栈中的重复次数和前一个字符串，进行字符串重复操作，并与之前的结果拼接。
class Solution {
public String decodeString(String s) {
Stack stack = new Stack();
char[] chars = s.toCharArray();
StringBuilder sb = new StringBuilder();
Integer multi = 0;
for (int i = 0; i < chars.length; i++) {
if (chars[i] >= 'a' && chars[i] <= 'z') {
sb.append(chars[i]);
}
if (chars[i] >= '0' && chars[i] <= '9') {
Integer tempInt = Integer.valueOf(String.valueOf(chars[i]));
multi = (multi * 10) + tempInt;
}
if (chars[i] == '[') {
stack.push(sb.toString());
sb.setLength(0);
stack.push(multi);
multi = 0;
}
if (chars[i] == ']') {
Integer tempMulti = (Integer) stack.pop();
String tempStr = sb.toString();
while (tempMulti > 1) {
sb.append(tempStr);
tempMulti--;
}
String stackStr = (String) stack.pop();
sb.insert(0, stackStr);
}
}
return sb.toString();
}
}递归法
通过递归模拟栈的操作，利用函数调用处理嵌套结构。每次遇到 [ 开启新递归层级，遇到 ] 结束当前层级并返回结果。关键变量如下：
静态索引
i：全局跟踪字符处理位置（需注意线程安全问题）preMulti：当前递归层需要重复的次数（由上一层传入）multi：当前累积的数字值（用于遇到[时传给下一层）
注意，decodeString 会重置i = 0 是因为 LeetCode 执行测试用例的时候，如果代码遇到 static变量，是不会重置值的，所以我们人工重置 i 的值。
class Solution {
private static int i = 0;
public String decodeString(String s) {
char[] arr = s.toCharArray();
String result = doDecodeString(arr, 0);
i = 0;
return result;
}
public String doDecodeString(char[] arr, int preMulti) {
int multi = 0;
StringBuilder sb = new StringBuilder();
while (i < arr.length) {
char a = arr[i];
if (a >= '0' && a <= '9') {
multi = Integer.parseInt(String.valueOf(a)) + multi * 10;
} else if (a == '[') {
i++;
sb.append(doDecodeString(arr, multi));
multi = 0;
} else if (a >= 'a' && a <= 'z') {
sb.append(a);
} else if (a == ']') {
String s = sb.toString();
while (preMulti-- > 1) {
sb.append(s);
}
return sb.toString();
}
i++;
}
return sb.toString();
}
}