来⾃LeetCode-20
给定⼀个只包括 '(',')','{','}','[',']' 的字符串,判断字符串是否有效。
有效字符串需满⾜:
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
分析:判断括号是否可以成对,建议使⽤栈进⾏判断
记住我我们对给定的字符串 s 进⾏遍历,当我们遇到⼀个左括号时,我们会期望在后续的遍历中,有⼀个相同类型的右括号将其闭合。由于后遇到的左括号要先闭合,因此我们可以将这个左括号放⼊栈顶。
当我们遇到⼀个右括号时,我们需要将⼀个相同类型的左括号闭合。此时,我们可以取出栈顶的左括号并判断它们是否是相同类型的括号。如果不是相同的类型,或者栈中并没有左括号,那么字符串 ss ⽆效,
返回 \text{False}False。为了快速判断括号的类型,我们可以使⽤哈希映射(HashMap)存储每⼀种括号。哈希映射的键为右括号,值为相同类型的左括号。
在遍历结束后,如果栈中没有左括号,说明我们将字符串 ss 中的所有左括号闭合,返回 True,否则返回False。
class Solution:
def isValid(self, s: str) -> bool:
if len(s) % 2 == 1:
return False #有效字符串的长度⼀定为偶数,因此如果字符串的长度为奇数,我们可以直接返回False,省去后续的遍历判断过程
pairs = {
")": "(",
"]": "[",
"}": "{",
} #⽤字典来把左右括号对应关系存储
stack = list()
for ch in s:
if ch in pairs:
if not stack or stack[-1] != pairs[ch]:
return False
stack.pop()
else:
stack.append(ch)
return not stack #匹配完成,判断stack是否为空。不为空则return false
发布评论