LeetCode20:有效的括号(逆波兰式)

2020年3月4日 评论 425 views 949字阅读3分9秒

前言

本系列文章为《leetcode》刷题笔记。

题目位置:力扣中国

题目

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

有效字符串需满足:

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。

示例 1:

输入: "()"
输出: true

示例 2:

输入: "()[]{}"
输出: true

示例 3:

输入: "(]"
输出: false

示例 4:

输入: "([)]"
输出: false

示例 5:

输入: "{[]}"
输出: true

思路

这是一个典型的逆波兰式,我的思路是利用栈先入后出的特点来解这一题。遍历一遍,遇到左括号就入栈,遇到右括号就出栈,前提是出栈之前需要判断栈顶最后一个元素是否和右括号成对,遇到其他就跳过。

边界条件:
1. 字符串内的字符串是奇数个,直接返回false(仅适用于 只有 括号的情况,如果有字母就不行了)
2. 没有左括号,就没有入栈,所以需要判断栈长度
4. 括号包括号{[]}

时间复杂度 O(N):正确的括号组合需要遍历 1 遍 s;
空间复杂度 O(N):哈希表和栈使用线性的空间大小。

代码

Go

func isLeft(c uint8) bool {
    return ('{' == c) || ('[' == c) || ('(' == c)
}

func isRight(c uint8) bool {
    return ('}' == c) || (']' == c) || (')' == c)
}

func isOk(c1 uint8, c2 uint8) bool {
    return ('{' == c1 && c2 == '}') || ('[' == c1 && ']' == c2) || ('(' == c1 && ')' == c2)
}

func isValid(s string) bool {
    if len(s)%2!=0 {
        return false
    }
    stack := make([]uint8, len(s))
    current := -1
    for i := 0; i < len(s); i++ {
        if isLeft(s[i]) {
            current++
            stack[current] = s[i]
        } else if isRight(s[i]) {
            if current != -1 && isOk(stack[current], s[i]) {
                current--
            } else {
                return false
            }
        }
    }
    return current == -1
}
weinxin
公众号
在号内与我交流,回复【资源】获取技术大礼包
小熊