leetcode-20

date
‣
slug
leetcode-20
status
Published
tags
Leetcode
summary
type
Post

题目

给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，’]’ 的字符串，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
示例 1:
输入: "()"
输出: true
示例 2:
输入: "()[]{}"
输出: true
示例 3:
输入: "(]"
输出: false
示例 4:
输入: "([)]"
输出: false
示例 5:
输入: "{[]}"
输出: true

思路

我们先分析一个有效的括号有什么特点
显然需要满足
  1. 同种类型括号配对 如 ( ) { } [ ]
  1. 括号闭合顺序一致 如 ([]) 而不是 (][)
通过分析以上几点我们得出
  1. 这个字符串的长度应该是 2 的倍数
      2. 显而易见，不是 2 的倍数的字符串里的括号一定不闭合
  1. 先出现的括号要在最后闭合
      2. 这提示我们要使用 栈 这样的先入后出的数据结构
那么，我们先遍历字符串，让之中的左括号入栈直到遇到右括号
让右括号匹配到它对于的左括号
利用一个 map 即可
pairs := map[byte]byte{
        '}':'{',
        ']':'[',
        ')':'('}
然后检查栈顶是否为对应的左括号
是则让其出栈
不是则这是非法字符串
最终栈内元素为 0 时，字符串有效
否则无效

题解

func isValid(s string) bool {
    if len(s)%2 != 0 {
        return false
    }
    pairs := map[byte]byte{
        '}':'{',
        ']':'[',
        ')':'('}
    var stack []byte
    for i:=0; i<len(s); i++{
        _, ok := pairs[s[i]]
        if ok {
            if len(stack) == 0 || stack[len(stack)-1] != pairs[s[i]] {
                return false
            }
            stack = stack[:len(stack)-1]
        } else {
            stack = append(stack, s[i])
        }
    }
    return len(stack) == 0
}

总结

先入后出 => 栈
匹配 => Map

© AlotOfBlahaj 2022 - 2025