LeetCode(Python)—— 有效的括号(简单)

LeetCode(Python)—— 有效的括号(简单)给定一个只包括'(‘,’)’,'{‘,’}’,'[‘,’]’的字符串s,判断字符串是否有效。

LeetCode(Python)——

有效的括号

概述:给定一个只包括 ‘(‘,’)’,'{‘,’}’,'[‘,’]’ 的字符串 s ,判断字符串是否有效。有效字符串需满足:左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。每个右括号都有一个对应的相同类型的左括号。

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

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

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

方法一:栈

我们遍历给定的字符串 。当我们遇到一个左括号时,我们会期望在后续的遍历中,有一个相同类型的右括号将其闭合。由于后遇到的左括号要先闭合,因此我们可以将这个左括号放入栈顶。

当我们遇到一个右括号时,我们需要将一个相同类型的左括号闭合。此时,我们可以取出栈顶的左括号并判断它们是否是相同类型的括号。如果不是相同的类型,或者栈中并没有左括号,那么字符串 s 无效,返回 False 。为了快速判断括号的类型,我们可以使用哈希表存储每一种括号。哈希表的键为右括号,值为相同类型的左括号。

在遍历结束后,如果栈中没有左括号,说明我们将字符串 ss 中的所有左括号闭合,返回 True ,否则返回 False

注意到有效字符串的长度一定为偶数,因此如果字符串的长度为奇数,我们可以直接返回 False ,省去后续的遍历判断过程。

话不多说,上代码!

class Solution:
    def isValid(self, s: str) -> bool:
        dict = {"(":")", "{":"}", "[":"]"}
        if len(s) % 2 == 1: # 长度为奇数
            return False

        stack = []
        for i in s:
            if i in dict:
                stack.append(i) # 入栈
            else:
                if stack != [] and i == dict[stack[-1]]: # 括号匹配正确
                    stack.pop() # 出栈
                else:
                    return False

        if stack == []: # 栈空,则全部通过判断
            return True
        else:
            return False

总结

思路清晰,代码难写!

今天的文章LeetCode(Python)—— 有效的括号(简单)分享到此就结束了,感谢您的阅读,如果确实帮到您,您可以动动手指转发给其他人。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/32886.html

(0)
编程小号编程小号

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注