HWA_29leetcode20有效的括号

题目

题解

classSolution:defisValid(self,s:str)->bool:# 当字符串⻓度为奇数的时候，属于⽆效情况，直接返回 Falseiflen(s)%2==1:# ⽆效情况，返回 FalsereturnFalse# 构建⼀个栈，⽤来存储括号stack=list()# 遍历字符串数组中的所有元素forcins:# 如果字符为左括号 ( ，那么就在栈中添加对左括号 （ifc=='(':# 添加对左括号 （stack.append('(')# 如果字符为左括号 [ ，那么就在栈中添加对左括号 [elifc=='[':# 添加对应的右括号 ]stack.append('[')# 如果字符为左括号 { ，那么就在栈中添加对左括号 {elifc=='{':# 添加对应的右括号 }stack.append('{')# 否则的话，说明此时 c 是 ）] } 这三种符号中的⼀种else:# 如果栈已经为空，⽽现在遍历的字符 c 是 ）] } 这三种符号中的⼀种# 找不到可以匹配的括号，返回 False# ⽐如这种情况 }{，直接从右括号开始，此时栈为空ifnotstack:returnFalse# 如果栈不为空，获取栈顶元素top=stack[-1]# 将栈顶元素和此时的元素 c 进⾏⽐较，如果相同，则将栈顶元素移除if(top=='('andc==')')or(top=='['andc==']')or(top=='{'andc=='}'):# 移除栈顶元素stack.pop()else:# 如果不相同，说明不匹配，返回 FalsereturnFalse# 遍历完整个字符数组，判断栈是否为空# 如果栈为空，说明字符数组中的所有括号都是闭合的# 如果栈为空，说明有未闭合的括号returnnotstack

图解

1遇到左括号把它压入栈中

2遇到右括号，弹出栈顶元素，与他比较

这是匹配的，所以把右括号弹出
只要不是匹配的，就不断地压入
{
但是此时是匹配地，所以弹出栈顶的[

如此迭代
遍历完后如果栈是空的，就认为是有效的字符串

看一下无效的字符串

这也是无效的