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
}