20. 有效的括号
题目：给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。有效字符串需满足：左括号必须用相同类型的右括号闭合；左括号必须以正确的顺序闭合；注意空字符串可被认为是有效字符串。
思路：利用栈先进后出的特性，若遇到左括号入栈，遇到右括号时将对应栈顶左括号出栈，则遍历完所有括号后 stack 仍然为空。建立哈希表 dic 构建左右括号对应关系：key为左括号，value 为右括号。
代码：
复杂度分析：正确的括号组合需要遍历 1 遍，故时间复杂度O(n)；存储哈希表，空间复杂度O(n).class Solution:
def isValid(self, s: str) -> bool:
if len(s)%2==1:
return False
stackItem=[]
stack_l={')':'(',']':'[','}':'{'}
strlist=list(s)
for item in strlist:
if item in stack_l.values():
stackItem.append(item)
elif item in stack_l.keys():
if len(stackItem)==0:
return False
if stack_l[item]==stackItem[-1]:
stackItem.pop()
else:
return False
if len(stackItem)==0:
return True
else:
return False 
vivo公司福利 364人发布
查看23道真题和解析
