友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
394. 字符串解码
给定一个经过编码的字符串，返回它解码后的字符串。
编码规则为: 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 <= 30 -
s由小写英文字母、数字和方括号[]组成 -
s保证是一个 有效 的输入。 -
s中所有整数的取值范围为[1, 300]
思路分析
主要就是一个栈操作。不过，还需要注意一些细节。
使用递归处理时，最重要的是递归一次，要把括号层数减少一层，否则只能原地踏步。
-
一刷
-
二刷
-
三刷
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/**
* Runtime: 1 ms, faster than 64.03% of Java online submissions for Decode String.
* Memory Usage: 37.4 MB, less than 5.68% of Java online submissions for Decode String.
*
* @author D瓜哥 · https://www.diguage.com
* @since 2020-01-28 22:08
*/
public String decodeString(String s) {
if (Objects.isNull(s) || s.length() == 0) {
return "";
}
Deque<Integer> nums = new LinkedList<>();
Deque<String> strings = new LinkedList<>();
int num = 0;
StringBuilder result = new StringBuilder();
for (char c : s.toCharArray()) {
if (c == '[') {
nums.addLast(num);
strings.addLast(result.toString());
num = 0;
result = new StringBuilder();
} else if (c == ']') {
StringBuilder sb = new StringBuilder();
Integer n = nums.removeLast();
for (int i = 0; i < n; i++) {
sb.append(result);
}
result = new StringBuilder(strings.removeLast() + sb.toString());
} else if (Character.isDigit(c)) {
num = num * 10 + (c - '0');
} else if (Character.isLetter(c)) {
result.append(c);
}
}
return result.toString();
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2024-09-18 16:05:13
*/
int idx = 0;
public String decodeString(String s) {
StringBuilder sb = new StringBuilder();
while (idx < s.length()) {
char c = s.charAt(idx);
if ('0' <= c && c <= '9') {
sb.append(dfs(s));
} else {
sb.append(c);
idx++;
}
}
return sb.toString();
}
private String dfs(String s) {
int cnt = 0;
boolean isEnd = false;
StringBuilder sb = new StringBuilder();
while (idx < s.length()) {
char c = s.charAt(idx);
if ('0' <= c && c <= '9') {
if (isEnd) {
sb.append(dfs(s));
continue;
}
int num = c - '0';
if (cnt == 0) {
cnt = num;
} else {
cnt = 10 * cnt + num;
}
idx++;
} else if ('a' <= c && c <= 'z') {
sb.append(c);
idx++;
} else if (c == '[') {
isEnd = true;
idx++;
} else if (s.charAt(idx) == ']') {
idx++;
break;
}
}
StringBuilder result = new StringBuilder();
for (int j = 0; j < cnt; j++) {
result.append(sb);
}
return result.toString();
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2025-10-14 19:36:59
*/
public String decodeString(String s) {
StringBuilder sb = new StringBuilder();
int index = 0;
while (index < s.length()) {
char c = s.charAt(index);
if ('a' <= c && c <= 'z') {
sb.append(c);
index++;
} else {
int start = index;
int left = 0, right = -1;
while (index < s.length() && right < left) {
char c1 = s.charAt(index);
if (c1 == '[') {
left++;
} else if (c1 == ']') {
if (right == -1) {
right = 1;
} else {
right++;
}
}
index++;
}
String part = s.substring(start, index - 1);
int i1 = part.indexOf("[");
int repeat = Integer.parseInt(part.substring(0, i1));
String is = decodeString(part.substring(i1 + 1));
sb.append(is.repeat(repeat));
}
}
return sb.toString();
}