Day.11 Decode String

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!