Fork me on GitHub

Leetcode-394-字符串解码

这是崔斯特的第一百零六篇原创文章

努力、奋斗

问题

给定一个经过编码的字符串,返回它解码后的字符串。

编码规则为: k[encoded_string],表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。

你可以认为输入字符串总是有效的;输入字符串中没有额外的空格,且输入的方括号总是符合格式要求的。 此外,你可以认为原始数据不包含数字,所有的数字只表示重复的次数 k ,例如不会出现像3a2[4]的输入。

示例

1
2
3
s = "3[a]2[bc]", 返回 "aaabcbc".
s = "3[a2[c]]", 返回 "accaccacc".
s = "2[abc]3[cd]ef", 返回 "abcabccdcdcdef".

思路

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
输入:'3[a2[c]]'
初始化栈: 栈nums 存要重复的次数k,栈str 存字符串
遍历字符串:
指针指向字符'3',为数字
num暂存数字3
继续遍历,遇到字符'['
循环次数num入栈nums,空字符串res入栈str
nums: 3 res: ''
num置为0,str置空
继续遍历,遇到字符'a',为字母
空字符串res拼接字母'a',res='a'
继续遍历,遇到字符'2',为数字
num暂存数字2
继续遍历遇到字符'['
num入栈nums,res入栈str
nums: 3 -> 2 str: '' -> 'a'
num置为0,str置空
继续遍历,遇到字符'c',为字母
空字符串res拼接字母'c',res='c'
继续遍历遇到字符']'
nums弹出栈顶元素:当前字符串重复次数2
res = res*2 = 'cc'
str弹出栈顶元素'a'与res拼接并入栈:
res = 'a'+'cc'='acc'
str: '' -> 'acc'
继续遍历遇到字符']'
nums弹出栈顶元素:当前字符串重复次数3
res = res*3 = 'accaccacc'
str弹出栈顶元素空字符串''与res拼接并入栈:
res=''+'accaccacc'='accaccacc'
str: 'accaccacc'
结束返回res

注意:

  • 由于重复次数可能大于10,所以暂存数字时要适当处理,如 num*10+当前数字
  • 在c++里可以直接修改拼接字符,但Java不支持运算符重载,可以借助 StringBuilder 或 StringBuffer 类。
  • 用栈暂存的逻辑与递归基本一致,可以理解为用递归实现栈。
  • python没有栈这种数据结构,可以用 list() 数组或双端队列 deque()
  • python可以只用一个栈以元组的形式重复次数和字符串,如(num,res)

利用栈

JAVA

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
public class Solution {
public String decodeString(String s) {
Stack<StringBuilder> str = new Stack<>();
Stack<Integer> nums = new Stack<>();
StringBuilder res = new StringBuilder();
int num = 0;
for (char c : s.toCharArray()) {
if (c == '[') {
str.push(res);
nums.push(num);
num = 0;
res = new StringBuilder();
} else if (c == ']') {
StringBuilder stringBuilder = new StringBuilder();
for (int i = nums.pop(); i > 0; i--) {
stringBuilder.append(res);
}
res = str.pop().append(stringBuilder);
} else if (c >= '0' && c <= '9') {
num = num * 10 + (c - '0');
} else {
res.append(c);
}
}
return res.toString();
}
public static void main(String[] args) {
String s = "3[a]2[bc]";
System.out.println(new Solution().decodeString(s));
}
}

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
def decodeString(self, s: str) -> str:
stack, res, num = [], '', 0
for i in s:
if i.isdigit():
num = num * 10 + int(i)
elif i.isalpha():
res += i
elif i == '[':
stack.append((res, num))
res, num = '', 0
else:
last_str, this_num = stack.pop()
res = last_str + this_num * res
return res
c = Solution().decodeString('3[a2[c]]') # aaabcbc
print(c)

Go

发现一种解法:倒序遍历字符串s,如果不是[则直接入栈;遇到[时,先找出[前边的数字nums表示为k,然后找出编码字符串encodedStr,重复k次入栈,跳过数字继续遍历

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
package main
import (
"fmt"
"strconv"
"strings"
)
func decodeString(s string) string {
stack := make([]string, 0)
for i := len(s) - 1; i >= 0; {
if s[i] == '[' {
nums := make([]string, 0)
for j := i - 1; j >= 0; j-- {
if s[j] >= '0' && s[j] <= '9' {
nums = append(nums, string(s[j]))
} else {
break
}
}
reverse(nums)
k, _ := strconv.Atoi(strings.Join(nums, ""))
encodedStr := make([]string, 0)
for stack[len(stack)-1] != "]" {
encodedStr = append(encodedStr, stack[len(stack)-1])
stack = stack[:len(stack)-1]
}
stack = stack[:len(stack)-1]
reverse(encodedStr)
for j := 0; j < k; j++ {
stack = append(stack, encodedStr...)
}
i -= len(nums)
} else {
stack = append(stack, string(s[i]))
}
i -= 1
}
reverse(stack)
return strings.Join(stack, "")
}
func reverse(arr []string) {
length := len(arr)
for i := 0; i < length/2; i++ {
arr[i], arr[length-i-1] = arr[length-i-1], arr[i]
}
}
func main() {
s := "3[a]2[bc]"
r := decodeString(s)
fmt.Println(r)
}

惊了惊了,这么牛逼

利用递归

JAVA

将 s.length() 的值以参数传递,减少重复调用 length() 造成的时间损耗

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
public class Solution {
private int i = -1;
public String decodeString(String s) {
return dfs(s.toCharArray(), s.length()).toString();
}
private StringBuilder dfs(char[] chars, int len) {
int num = 0;
StringBuilder str = new StringBuilder();
while (++i < len) {
if (chars[i] >= '0' && chars[i] <= '9') {
num = num * 10 + (chars[i] - '0');
} else if (chars[i] == '[') {
StringBuilder tmp = dfs(chars, len);
while (--num >= 0) {
str.append(tmp);
}
num = 0;
} else if (chars[i] == ']') {
return str;
} else {
str.append(chars[i]);
}
}
return str;
}
public static void main(String[] args) {
String s = "3[a]2[bc]";
System.out.println(new Solution().decodeString(s));
}
}

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
i = -1
def decodeString(self, s: str) -> str:
res, num = '', 0
while self.i < len(s) - 1:
self.i += 1
if s[self.i].isdigit():
num = num * 10 + int(s[self.i])
elif s[self.i].isalpha():
res += s[self.i]
elif s[self.i] == '[':
res += self.decodeString(s) * num
num = 0
else:
return res
return res
if __name__ == '__main__':
assert Solution().decodeString('3[a]2[bc]') == 'aaabcbc'
assert Solution().decodeString('3[a2[c]]') == 'accaccacc'
assert Solution().decodeString('2[abc]3[cd]ef') == 'abcabccdcdcdef'