20 有效的括号
题目描述
给定一个只包括 '(',')','{','}','[',']' 的字符串 s ,判断字符串是否有效。
有效字符串需满足:
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
思路
1、将python中的list看作栈,左括号入栈,右括号与左括号匹配则出栈。长度为奇数并且入栈为右括号时返回False
2、参考自讨论区,逐步替代成对的括号,代码见讨论区。
代码
class Solution:
def isValid(self, s: str) -> bool:
if len(s)%2==1:
return False
temp = []
rule = {'(':')', '[':']', '{':'}'}
for item in s:
if not temp or rule[temp[-1]] !=item:
if item in rule: # 右括号入栈返回False,并且防止字典中key无右括号
temp.append(item)
else:
return False
else:
temp.pop()
return (not temp)