leetcode-20. 有效的括号
一、问题描述
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
示例 1:
输入: "()" 输出: true
示例 2:
输入: "()[]{}" 输出: true
示例 3:
输入: "(]" 输出: false
示例 4:
输入: "([)]" 输出: false
示例 5:
输入: "{[]}" 输出: true
二、代码和思路
1.首先定义开括号和闭括号的字符串，另外定义一个字典用来对应开闭括号
2.这里用一个lst来存储开括号（这里用了栈的概念），碰到开括号存在最后一个，碰到闭括号就拿lst的最后一个元素去匹配，匹配失败就返回false
3.最后检查lst是否还存在开括号，返回bool值len(lst)==0
class Solution(object):
def isValid(self, s):
"""
:type s: str
:rtype: bool
"""
open_brackets='([{'
close_brackets =')]}'
brackets_dicts={')':'(',']':'[','}':'{'}
lst=[]
i,n=0,len(s)
while i<n:
if s[i] in open_brackets:
lst.append(s[i])
if s[i] in close_brackets:
if len(lst)==0:return False
if brackets_dicts[s[i]] != lst.pop():
return False
i += 1
return len(lst)==0
三、运行结果