LeetCode 20. Valid Parentheses

题目

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.

分析

括号匹配问题

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution(object):
def isValid(self, s):
"""
:type s: str
:rtype: bool
"""
stack = []
dict = {"]":"[", "}":"{", ")":"("}
for char in s:
if char in dict.values():
stack.append(char)
elif char in dict.keys():
if stack == [] or dict[char] != stack.pop():
return False
else:
return False
return stack == []

点评

括号匹配问题,用栈解决,遍历字符串遇到左括号,直接入栈,遇到右括号,如果栈为空则返回 False,否则出栈,和字典里对应的左括号对比,不等则 return False,否则继续。
注意:遍历完之后,还需要判断一下栈是否是空的,如果是空的则输出 True