字符串解码

1. 题目描述

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

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

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

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

2. 思路

• 栈

3. 实现

3.1. 栈

• []rune版本

type ele struct {
	letters []rune
	multi   int
}

func decodeString(s string) string {

	runes := []rune(s)
	stack := make([]*ele, 0)
	currentLetters := make([]rune, 0)
	multi := 0
	for _, r := range runes {
		//遇到左括号，入栈
		if r == '[' {
			stack = append(stack, &ele{
				multi:   multi,
				letters: currentLetters,
			})
			currentLetters = make([]rune, 0)
			multi = 0
			//遇到右括号，出栈
		} else if r == ']' {
			e := stack[len(stack)-1]
			stack = stack[:len(stack)-1]

			letters := make([]rune, 0)
			for i := 0; i < e.multi; i++ {
				letters = append(letters, currentLetters...)
			}
			currentLetters = append(e.letters, letters...)

			//以下两个分支记录经过的数字和字符
		} else if r >= '0' && r <= '9' {
			multi = multi*10 + int(r-'0')
		} else {
			currentLetters = append(currentLetters, r)
		}
	}

	return string(currentLetters)
}

• bytes.Buffer版本

type ele struct {
	str   string
	multi int
}

func decodeString(s string) string {
	var multi int
	buf := bytes.NewBuffer([]byte{})
	var stack []*ele
	for _, r := range s {
		if r >= '0' && r <= '9' {
			multi = multi*10 + int(r-'0')
		} else if r >= 'a' && r <= 'z' {
			buf.WriteRune(r)
		} else if r == '[' {
			e := &ele{multi: multi, str: buf.String()}
			stack = append(stack, e)
			buf.Reset()
			multi = 0
		} else {
			e := stack[len(stack)-1]
			stack = stack[:len(stack)-1]
			temp := bytes.NewBuffer([]byte{})
			str := buf.String()
			for i := 0; i < e.multi; i++ {
				temp.WriteString(str)
			}
			buf.Reset()
			buf.WriteString(e.str)
			buf.WriteString(temp.String())
		}
	}
	return buf.String()
}

4. 参考

• 394. 字符串解码 - 力扣（LeetCode）