Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
An input string is valid if:
Open brackets must be closed by the same type of brackets. Open brackets must be closed in the correct order. Note that an empty string is also considered valid.
使用栈，遍历字符串，遇到左括号则入栈，右括号则出栈比对。
class Solution:
_parentheses = {
')': '(', '}': '{', ']': '['
}
def isValid(self, s: str) -> bool:
stack = []
for c in s:
if c in ('(', '{', '['):
stack.append(c)
else:
if not stack:
return False
cc = stack.pop()
if cc != self._parentheses.get(c):
return False
if stack:
return False
return True