leetcode 394. 字符串解码

题解

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

示例代码(go)

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
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]
}
}