来⾃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
发布评论