括号问之：20有效的括号

题目链接20.有效的括号

1、题目分析

字符串只有三种类型的括号，如果先有右括号一定不是有效的，如果每一个左括号都能匹配到右括号就算成功。

2、解题分析

• 初始话一个字典，包含三个键值对，就是三队括号
• 初始化两个字符串，一个包含左括号，一个包含右括号
• 进行for循环遍历
  • 如果是左括号直接添加到辅助栈
  • 如果是右括号且辅助站是空直接返回Fasle
  • 如果右括号与栈顶元素匹配就弹出栈顶元素
    • 否则返回Fasle
• 循环结束判断一下辅助栈是否为空
  • 如果为空，为所有的左括号找到了右括号
  • 否则就有没有配对成功的

3、代码

class Solution:def isValid(self, s: str) -> bool:dic = {'(':')','{':'}','[':']'}L = '({['R = ')}]'res = []if not s:return Truefor i in s:#如果是左括号直接添加到栈中if i in L:res.append(i)#如果是右括号,且栈为空,那么也就意味着先进右括号,不能形成有效括号对elif i in R and not res:return False#否则如果栈顶元素等于右括号,弹出栈顶元素,否则返回Falseelse:if dic[res[-1]]==i:res.pop()else:return False#如果最后的辅助栈为空就说明所有左括号都得到匹配了,否则返回Faslereturn not res

总结：括号问题一定是匹配最近的一个左括号，往往都是用辅助栈去解决问题。