394. 字符串解码
查看题目中等
字符串
中频
解法一：递归法
时间复杂度：O(n) | 空间复杂度：O(n) | 推荐使用
动画演示
准备就绪 - 输入字符串，然后点击开始
代码实现
class Solution {
String src;
int ptr;
public String decodeString(String s) {
src = s;
ptr = 0;
return getString();
}
public String getString() {
if (ptr == src.length() || src.charAt(ptr) == ']') {
// 递归终止条件
return "";
}
char cur = src.charAt(ptr);
int repTime = 1;
String ret = "";
if (Character.isDigit(cur)) {
// 解析数字
repTime = getDigits();
// 过滤左括号
++ptr;
// 递归解析括号内的字符串
String str = getString();
// 过滤右括号
++ptr;
// 构造字符串
while (repTime-- > 0) {
ret += str;
}
} else if (Character.isLetter(cur)) {
// 解析字母
ret = String.valueOf(src.charAt(ptr++));
}
// 继续解析剩余部分
return ret + getString();
}
public int getDigits() {
int ret = 0;
while (ptr < src.length() && Character.isDigit(src.charAt(ptr))) {
ret = ret * 10 + (src.charAt(ptr++) - '0');
}
return ret;
}
}
时间复杂度：O(n)
空间复杂度：O(n)
递归方法的核心思路是使用指针遍历字符串，遇到字母则直接添加到结果中；遇到数字则解析完整数字作为重复次数，然后跳过左括号，递归解析括号内的字符串，最后将递归结果重复指定次数后添加到结果中；遇到右括号则结束当前递归层并返回结果。递归终止条件是指针到达字符串末尾或遇到右括号。通过这种方式，可以自然处理嵌套的括号结构。
解法二：栈
时间复杂度：O(n) | 空间复杂度：O(n)
动画演示
准备就绪 - 输入字符串，然后点击开始
代码实现
import java.util.LinkedList;
import java.util.Collections;
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());
StringBuilder t = new StringBuilder();
String o = getString(sub);
// 构造字符串
while (repTime-- > 0) {
t.append(o);
}
// 将构造好的字符串入栈
stk.addLast(t.toString());
}
}
return getString(stk);
}
public String getDigits(String s) {
StringBuilder ret = new StringBuilder();
while (Character.isDigit(s.charAt(ptr))) {
ret.append(s.charAt(ptr++));
}
return ret.toString();
}
public String getString(LinkedList<String> v) {
StringBuilder ret = new StringBuilder();
for (String s : v) {
ret.append(s);
}
return ret.toString();
}
}
时间复杂度：O(n)
空间复杂度：O(n)
栈方法的核心思路是使用两个栈：一个存储重复次数，一个存储字符串。遍历输入字符串时，遇到数字则解析完整数字并存入数字栈；遇到字母则直接添加到当前字符串；遇到左括号则将当前字符串和重复次数压入栈中，并重置当前字符串和重复次数；遇到右括号则弹出数字栈顶元素作为重复次数，弹出字符串栈顶元素作为前缀，将当前字符串重复指定次数后与前缀拼接，作为新的当前字符串。最终当前字符串即为解码结果。