DeepSeek LeetCode 394. 字符串解码 Java实现

LeetCode 394. 字符串解码 – Java 实现

题目回顾

给定编码字符串，规则为 k[encoded_string]，表示方括号内的字符串重复 k 次。可嵌套。返回解码后的字符串。

例如：“3[a2[c]]” → “accaccacc”。

解法一：双栈（推荐，最直观）

用两个栈分别保存重复次数和进入括号前的已拼接字符串。

遍历每个字符：

字符 操作
数字 累积成多位数字 num
[ 将 num 和 res 入栈，重置 num=0、res=“”
] 弹出 count 和 prev，res = prev + res.repeat(count)
字母 res += c

class Solution {
public String decodeString(String s) {
Deque<Integer> countStack = new ArrayDeque<>();
Deque<String> strStack = new ArrayDeque<>();
StringBuilder res = new StringBuilder();
int num = 0;

for (char c : s.toCharArray()) {
if (Character.isDigit(c)) {
num = num * 10 + (c – '0'); // 处理多位数字
} else if (c == '[') {
countStack.push(num); // 保存重复次数
strStack.push(res.toString()); // 保存外层已拼好的串
num = 0;
res.setLength(0); // 重置，开始拼括号内
} else if (c == ']') {
int count = countStack.pop();
StringBuilder tmp = new StringBuilder(strStack.pop());
for (int i = 0; i < count; i++) {
tmp.append(res);
}
res = tmp;
} else {
res.append(c); // 普通字母
}
}
return res.toString();
}
}

解法二：递归（自顶向下解析）

遇到 [ 就递归解析子串，返回后按次数拼接，并继续从右括号之后处理。

class Solution {
private int i = 0; // 全局指针

public String decodeString(String s) {
StringBuilder res = new StringBuilder();
int num = 0;

while (i < s.length()) {
char c = s.charAt(i);
if (Character.isDigit(c)) {
num = num * 10 + (c – '0');
i++;
} else if (c == '[') {
i++; // 跳过 '['
String inner = decodeString(s); // 递归解析括号内
i++; // 跳过 ']'
for (int k = 0; k < num; k++) {
res.append(inner);
}
num = 0;
} else if (c == ']') {
return res.toString(); // 遇到右括号，返回给上层
} else {
res.append(c);
i++;
}
}
return res.toString();
}
}

解法三：单栈 + 记录（可选）

也可以只用一个栈存"次数 和 字符串"的配对对象，但双栈更清晰，这里略。

关键点

复杂度分析

· 时间复杂度：O(S)，S 为解码后字符串长度（每个字符的生成是必要的）。
· 空间复杂度：O(S)，栈与结果字符串。

示例验证

s = "3[a2[c]]"

c='3' num=3
c='[' push(3,""); num=0, res=""
c='a' res="a"
c='2' num=2
c='[' push(2,"a"); num=0, res=""
c='c' res="c"
c=']' count=2 prev="a" -> res = "a"+"c"*2 = "acc"
c=']' count=3 prev="" -> res = "" + "acc"*3 = "accaccacc" ✓

解法一在工程上最稳健，解法二代码更短，按需选用即可。