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,如果不是[则直接入栈;遇到[时,先找出[前边的数字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]
}
}