有效的括号
概述:给定一个只包括 ‘(‘,’)’,'{‘,’}’,'[‘,’]’ 的字符串 s ,判断字符串是否有效。有效字符串需满足:左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。每个右括号都有一个对应的相同类型的左括号。
输入:s = "()"
输出:true
输入:s = "()[]{}"
输出:true
输入:s = "(]"
输出:false
方法一:栈
我们遍历给定的字符串 s 。当我们遇到一个左括号时,我们会期望在后续的遍历中,有一个相同类型的右括号将其闭合。由于后遇到的左括号要先闭合,因此我们可以将这个左括号放入栈顶。
当我们遇到一个右括号时,我们需要将一个相同类型的左括号闭合。此时,我们可以取出栈顶的左括号并判断它们是否是相同类型的括号。如果不是相同的类型,或者栈中并没有左括号,那么字符串 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