有效的括号

题目描述

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

有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。

2. 左括号必须以正确的顺序闭合。

3. 每个右括号都有一个对应的相同类型的左括号。

示例 1：

输入：s = “()”
输出：true

示例 2：

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

示例 3：

输入：s = “(]”
输出：false

提示：

• 1 <= s.length <= 104
• s 仅由括号 ‘()[]{}’ 组成

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/valid-parentheses
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

我的答案

func isValid(s string) bool {
    // 栈
    // 创建一个数组来代替栈
    if len(s) % 2 == 1{
        return false
    }
    str := []byte{}
    // 遇左括号入栈，遇右括号判断其前一个是否为相匹配的左括号，若是，则两者都出栈，否则返回false
    flag := true
    for i:=0;i<len(s) && flag;i++{
        switch s[i]{
            case '(','{','[':
                str = append(str,s[i])
            case ')':
                if len(str) == 0{
                    flag = false
                    break
                }
                if str[len(str)-1] == '('{
                    str = str[:len(str)-1]
                }else{
                    flag = false
                }
            case '}':
                if len(str) == 0{
                    flag = false
                    break
                }
                if str[len(str)-1] == '{'{
                    str = str[:len(str)-1]
                }else{
                    flag = false
                }
            case ']':
                if len(str) == 0{
                    flag = false
                    break
                }
                if str[len(str)-1] == '['{
                    str = str[:len(str)-1]
                }else{
                    flag = false
                }
            default: break
        }
    }
    if len(str) != 0{
        flag = false
    }
    return flag
}

解题思路

栈是一个后进先出的队列，用在这里可以避免复杂的判断结构。但是，Go语言的标准库没有栈这种结构，我就手动实现了一个。

题解

func isValid(s string) bool {
	size := len(s)

	stack := make([]byte, size)
	top := 0

	for i := 0; i < size; i++ {
		c := s[i]
		switch c {
		case '(':
			stack[top] = c + 1 // '('+1 is ')'，ASCII码值
			top++
		case '[', '{':
			stack[top] = c + 2
			top++
		case ')', ']', '}':
			if top > 0 && stack[top-1] == c {
				top--
			} else {
				return false
			}
		}
	}

	return top == 0
}

根据 benchmark显示，极端情况下，可以减少 40% 的时间。

总结

• 栈的应用