LeetCode-394. 字符串解码 - sheep44044的小站

栈#

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

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

你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。

此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。

测试用例保证输出的长度不会超过 105。

示例 1：

1
输入：s = "3[a]2[bc]"
2
输出："aaabcbc"

示例 2：

1
输入：s = "3[a2[c]]"
2
输出："accaccacc"

示例 3：

1
输入：s = "2[abc]3[cd]ef"
2
输出："abcabccdcdcdef"

示例 4：

1
输入：s = "abc3[cd]xyz"
2
输出："abccdcdcdxyz"

思路

虽然看着很麻烦，其实逻辑挺简单的，和人脑想的顺序一样。

遇到了字母，那拿一个普通变量curStr储存
遇到了数字，那再拿一个普通变量curNum储存
遇到了[，需要暂存前面的字母和数字，那就存入栈了，继续处理括号里面的内容
遇到了]，可以组成一个string了，那就从栈后进先出，获取前面对应的字母和数字，拼接
重复操作

ps：可能是golang中像队列、栈这些都是用切片实现的，所以对栈没有太多感受

1
func decodeString(s string) string {
2
    strStack := []string{}
3
    numStack := []int{}
4

5
    curStr := ""
6
    curNum := 0
7

8
    for _, char := range s {
9
        if char >= '0' && char <= '9' {
10
            curNum = curNum*10 + int(char-'0')
11
        }else if char >= 'a' && char <= 'z' || char >= 'A' && char <= 'Z' {
12
            curStr += string(char)
13
        }else if char == '[' {
14
            numStack = append(numStack, curNum)
15
            curNum = 0
16

17
            strStack = append(strStack, curStr)
18
            curStr = ""
19
        }else {
20
            num := numStack[len(numStack)-1]
21
            numStack = numStack[:len(numStack)-1]
22

23
            str := strStack[len(strStack)-1]
24
            strStack = strStack[:len(strStack)-1]
25

26
            curStr = str + strings.Repeat(curStr, num)
27
        }
28
    }
29
    return curStr
30
}