20.E 有效的括号

Problem: 20. 有效的括号

思路

可以用slice模拟一个栈来实现。

首先用一个mapping来存储映射关系，以右括号为key，是为了在右括号与栈顶的左括号不匹配时立即退出。

遍历括号：

• 如果遇到右括号：

  • 如果栈为空，或者栈顶括号与当前括号不匹配，则返回false

  • 否则，栈顶括号出栈

• 否则，入栈

Code

var mapping = map[byte]byte{
	')': '(',
	']': '[',
	'}': '{',
}

func isValid(s string) bool {
	var stack []byte
	for i := range s {
		ch := s[i] //这种写法ch的类型是uint8,等同于byte。如果是for i, ch这种写法，ch的类型是int32，后续不太方便处理
		if _, ok := mapping[ch]; ok {
			if len(stack) == 0 || stack[len(stack)-1] != mapping[ch] {
				return false
			}

			stack = stack[0 : len(stack)-1]
		} else {
			stack = append(stack, ch)
		}
	}

	return len(stack) == 0
}