有效的括号

题目描述

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

有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。
3. 每个右括号都有一个对应的相同类型的左括号。

示例

输入：s = "()"
输出：true

输入：s = "()[]{}"
输出：true

输入：s = "(]"
输出：false

解题思路

自做

在做题的时候，我想到了栈这个后进先出的数据结构，正好适合这道题目。

因为左边的括号必须要有右边的括号与之对应，所以我们可以将左边的括号入栈，当遇到右边的括号时，我们将栈顶的括号出栈，判断是否与右边的括号相同。

// 0ms
func isValid(s string) bool {
    stack := NewStack()
    for _, v := range s {
        ns := fmt.Sprintf("%c", v)
        switch ns {
        case "(":
            stack.Push(ns)
        case "[":
            stack.Push(ns)
        case "{":
            stack.Push(ns)
        case ")":
            ls := stack.Pop()
            if ls != "(" {
                return false
            }
        case "]":
            ls := stack.Pop()
            if ls != "[" {
                return false
            }
        case "}":
            ls := stack.Pop()
            if ls != "{" {
                return false
            }
        }
    }
    // 判断栈是否为空，为空则说明所有括号都匹配成功
    if stack.Pop() != nil {
        return false
    }
    return true
}

// 通过slice实现栈
type Item interface{}

type ItemStack struct {
    items []Item
    lock  sync.RWMutex
}

func NewStack() *ItemStack {
    s := &ItemStack{}
    s.items = []Item{}
    return s
}

func (s *ItemStack) Print() {
    fmt.Println(s.items)
}

func (s *ItemStack) Push(t Item) {
    s.lock.Lock()
    s.lock.Unlock()
    s.items = append(s.items, t)
}

func (s *ItemStack) Pop() Item {
    s.lock.Lock()
    defer s.lock.Unlock()
    if len(s.items) == 0 {
        return nil
    }
    item := s.items[len(s.items)-1]
    s.items = s.items[0 : len(s.items)-1]
    return item
}

学习

官方解法相似

总结

今天刷了一道简单的题目，有效的括号。自己的解法是通过栈来实现，时间复杂度为 O(n)。不过Golang中没有栈的数据结构，所以我通过slice来实现了一个栈。

学习了栈的使用，今天需要记住的是：栈是一种后进先出的数据结构，队列则是一种先进先出的数据结构。

明天继续刷题，加油！