LeetCode-20-有效括号

给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。

https://leetcode-cn.com/problems/valid-parentheses/

思路

• 滑动窗口

type stack struct {
	arr []int32
}

func (s *stack) push(c int32) {
	s.arr = append(s.arr, c)
}
func (s *stack) pop() int32 {
	var t int32
	if !s.isEmpty() {
		t = s.arr[len(s.arr)-1]
		s.arr = s.arr[:len(s.arr)-1]
	}
	return t
}
func (s *stack) isEmpty() bool {
	if len(s.arr) == 0 {
		return true
	}
	return false
}

func isValid(s string) bool {
	m := map[int32]int32{
		')': '(',
		']': '[',
		'}': '{',
	}
	sta := stack{arr: make([]int32, 0, 0)}
	for _, v := range s {
		if mv, ok := m[v]; ok {
			if sta.pop() != mv {
				return false
			}
		} else {
			sta.push(v)
		}
	}
	if sta.isEmpty() {
		return true
	}
	return false
}