Leetcode #394. Decode String

題目簡單來說要用數字乘以[]裡面的字串
ex.
Input: s = "3[a]2[bc]"
Output: "aaabcbc"

Input: s = "3[a2[c]]"
Output: "accaccacc"

Input: s = "3[a2[c]]"
Output: "accaccacc"

數字後面一定是一個"["，每個"["都會有一個"]"，數字範圍在1~300，input格式都是合法的。

防雷
防雷
防雷

這一題要用之前講過的stack來解！
ex. 3[a2[cq]]

基本上在遇到"]"之前，不需要做任何事情，把值都推到stack裡面。
stack: 3 [ a 2 [ c q

在q後面會遇到第一個"]"你再從stack裡面把值都pop出來，直到遇到"["，再去乘以前面的數值，最後放回去stack。

num: 2
str: cq
stack: 3 [ a 

把乘完的值放回去stack

stack: 3 [ a cqcq

再遇到最後一個"]"，同樣的流程，就可以得出答案了

num: 3
str: acqcq
stack:

答案: acqcqacqcqacqcq

程式:

// 昨天寫的stack
type Stack struct {
	nodes []string
}

func (s *Stack) Push(val string) {
	s.nodes = append(s.nodes, val)
}

func (s *Stack) Pop() string {
	if len(s.nodes) == 0 {
		return ""
	}

	res := s.nodes[len(s.nodes)-1]
	s.nodes = s.nodes[0 : len(s.nodes)-1]

	return res
}

func decodeString(s string) string {
	stack := Stack{}
	for _, v := range s {
		// 遇到']'之前 都直接往stack推
		if v != ']' {
			stack.Push(string(v))
			continue
		}

		// 遇到']'了
		str := ""
		index := len(stack.nodes) - 1
		for index >= 0 {
			// 找到'['跳出迴圈
			if stack.nodes[index] == "[" {
				stack.Pop() // 把'['拿掉
				index--
				break
			}

			str = string(stack.Pop()) + str
			index--
		}

		// 處理數字
		num := ""
		for index >= 0 {
			_, err := strconv.Atoi(stack.nodes[index])
			if err != nil {
				// 不是數字了 跳出迴圈
				break
			}

			num = stack.Pop() + num
			index--
		}

		count, _ := strconv.Atoi(num)
		stack.Push(strings.Repeat(str, count))
	}

	return strings.Join(stack.nodes, "")
}

leetcode 執行結果

Runtime: 0 ms, faster than 100.00% of Go online submissions for Decode String.
Memory Usage: 2 MB, less than 71.33% of Go online submissions for Decode String.

這個解法算好理解，不過程序碼看起來有點多XD，stack可以用slice來取代，會少一個struct，大家可以看看其他人的解法哦！

明天來講Queue! byebye!