用栈实现leetcode第394题:字符串解码(带图解)
文章目录
题目描述
给定一个经过编码的字符串,返回它解码后的字符串。
编码规则为: k[encoded_string],表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
你可以认为输入字符串总是有效的;输入字符串中没有额外的空格,且输入的方括号总是符合格式要求的。
此外,你可以认为原始数据不包含数字,所有的数字只表示重复的次数 k ,例如不会出现像 3a 或 2[4] 的输入。
示例:
s = "3[a]2[bc]", 返回 "aaabcbc".
s = "3[a2[c]]", 返回 "accaccacc".
s = "2[abc]3[cd]ef", 返回 "abcabccdcdcdef".
思路
借助栈来完成。
- 计算串出现的次数,即
[左侧的数字。 - 如果是字母,直接入栈
- 如果是
[,则将计算好的次数入栈 -
如果是
],开始弹栈- 如果是字母,则进行拼接s。(注意后弹栈出的元素放在前面,需要使用insert(0, ch))
- 如果是数字n,则将n个s进行拼接,然后入栈。并结束弹栈。
举例
计算3[a4[bc]]的结果。
| 3 | [ | a | 4 | [ | b | c | ] | ] | |
|---|---|---|---|---|---|---|---|---|---|
| ↑ |
stack = {}
count = 3
| 3 | [ | a | 4 | [ | b | c | ] | ] | |
|---|---|---|---|---|---|---|---|---|---|
| ↑ |
stack = {3}
count = 0
| 3 | [ | a | 4 | [ | b | c | ] | ] | |
|---|---|---|---|---|---|---|---|---|---|
| ↑ |
stack = {3, a}
count = 0
| 3 | [ | a | 4 | [ | b | c | ] | ] | |
|---|---|---|---|---|---|---|---|---|---|
| ↑ |
stack = {3, a}
count = 4
| 3 | [ | a | 4 | [ | b | c | ] | ] | |
|---|---|---|---|---|---|---|---|---|---|
| ↑ |
stack = {3, a, 4}
count = 0
| 3 | [ | a | 4 | [ | b | c | ] | ] | |
|---|---|---|---|---|---|---|---|---|---|
| ↑ |
stack = {3, a, 4, b}
count = 0
| 3 | [ | a | 4 | [ | b | c | ] | ] | |
|---|---|---|---|---|---|---|---|---|---|
| ↑ |
stack = {3, a, 4, b, c}
count = 0
| 3 | [ | a | 4 | [ | b | c | ] | ] |
|---|---|---|---|---|---|---|---|---|
| ↑ |
stack = {3, a, bc, bc, bc, bc}
count = 0
因为遇到 ],需要弹栈。将弹出的字符进行拼接(后出栈的拼接在字符串前面),知道遇到数字n,则将N个字符串入栈。所以需要将4个"bc"字符串入栈
| 3 | [ | a | 4 | [ | b | c | ] | ] |
|---|---|---|---|---|---|---|---|---|
| ↑ |
stack = {abcbcbcbc, abcbcbcbc, abcbcbcbc}
count = 0
因为遇到 ],需要弹栈。将弹出的字符进行拼接(后出栈的拼接在字符串前面),知道遇到数字n,则将N个字符串入栈。所以需要将3个"abcbcbcbc"字符串入栈
遍历完成之后,将栈中数据拼接即可得到最终结果:abcbcbcbcabcbcbcbcabcbcbcbc
代码
public String decodeString(String s) {
char[] chs = s.toCharArray();
Stack<String> stack = new Stack<>();
int count = 0;
for (int i = 0, len = chs.length; i < len; i++) {
char ch = chs[i];
if (ch >= '0' && ch <= '9') {
// 统计数字。eg: 12是2个字符进行处理的
count = 10 * count + (ch - '0');
} else if (ch == '[') {
// 遇到[,则将数字入栈
stack.push(String.valueOf(count));
count = 0;
} else if ((ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z')) {
// 字母直接入栈
stack.push(String.valueOf(ch));
} else if (ch == ']') {
// 遇到],开始弹栈处理字符串解码
StringBuilder sb = new StringBuilder();
while (!stack.empty()) {
String s1 = stack.pop();
if (isDigital(s1)) {
int j = 0;
while (j++ < Integer.parseInt(s1)) {
stack.push(sb.toString());
}
break;
} else {
sb.insert(0, s1);
}
}
}
}
StringBuilder res = new StringBuilder();
while (!stack.empty()) {
res.insert(0, stack.pop());
}
return res.toString();
}
private boolean isDigital(String s) {
try {
Integer.parseInt(s);
return true;
} catch (Exception e) {
return false;
}
}
评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论