Decode String

1. Problem Description

Given an encoded string, return its decoded string.

The encoding rule is k[encoded_string], meaning that the encoded_string inside the square brackets is repeated exactly k times. Note that k is guaranteed to be a positive integer.

You may assume the input string is always valid; there are no extra spaces, and the brackets always follow the required format.

You may also assume the original data contains no digits. All digits represent the repetition count k, so inputs such as 3a or 2[4] do not occur.

2. Approach

• Stack

3. Implementation

3.1. Stack

• []rune version

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 {
		// On a left bracket, push onto the stack
		if r == '[' {
			stack = append(stack, &ele{
				multi:   multi,
				letters: currentLetters,
			})
			currentLetters = make([]rune, 0)
			multi = 0
			// On a right bracket, pop from the stack
		} 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...)

			// The following two branches record encountered digits and characters
		} else if r >= '0' && r <= '9' {
			multi = multi*10 + int(r-'0')
		} else {
			currentLetters = append(currentLetters, r)
		}
	}

	return string(currentLetters)
}

• bytes.Buffer version

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. References

• 394. Decode String - LeetCode