20. 有效的括号
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
示例:
输入: "{[]}" -> true
输入: "([)]" -> false
解法1
用字典来存储括号对, 用Stack来记录遍历字符串的结果, 左括号入栈, 有对应的右括号就出栈
示例代码
class Solution:
def isValid(self, s):
if s is None or len(s) == 0: #排除异常情况, 字符串为空时返回True
return True
if len(s)%2 == 1: #排除异常情况, 字符串为奇数时返回False
return False
bracket = {'(':')','{':'}','[':']'} #把括号一一对应存入字典
stack = []
for each in s:
if each in bracket: #遍历字符串, 发现左括号入栈
stack.append(each)
else: #不是最括号的情况
if not stack or each != bracket[stack.pop()]:
return False #栈空, 即不是以最括号开头或不是从最后一个开衫对应, 返回False
return stack == [] #一一对应出栈则说明是有效括号
解法2
依然是最括号入栈, 有对应的右括号出栈, 相当于是简化版
示例代码:
def isValid(self, s):
a = {')':'(', ']':'[', '}':'{'} #右括号对应最括号的字典
l = [None] #设置None排除空值的情况
for i in s:
if i in a and a[i] == l[-1]:
l.pop() #右括号, 且与最后一个最括号对应, 出栈
else:
l.append(i) #左括号入栈
return len(l)==1
