## Description

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

An input string is valid if:

1. Open brackets must be closed by the same type of brackets.
2. Open brackets must be closed in the correct order.

Note that an empty string is also considered valid.

Example 1:

Input: "()"
Output: true


Example 2:

Input: "()[]{}"
Output: true


Example 3:

Input: "(]"
Output: false


Example 4:

Input: "([)]"
Output: false


Example 5:

Input: "{[]}"
Output: true


## Solutions

### 1. Stack-先进后出

一般来讲这种匹配问题会涉及到先进后出的过程，很明显用 Stack，然而第一次手写果然还是很不优雅啊：

class Solution:
def isValid(self, s: str) -> bool:
if not s:
return True
stack = []
for c in s:
if not stack and (c == ')' or c == ']' or c == '}'):
return False
if c == '(' or c == '[' or c == '{':
stack.append(c)
else:
if c == ')' and stack[-1] == '(':
stack.pop()
continue
if c == ']' and stack[-1] == '[':
stack.pop()
continue
if c == '}' and stack[-1] == '{':
stack.pop()
continue
stack.append(c)
if stack:
return False
else:
return True
# 76/76 cases passed (32 ms)
# Your runtime beats 79.89 % of python3 submissions
# Your memory usage beats 100 % of python3 submissions (12.7 MB)


这种写法真是优雅，用上了字典！

class Solution:
def isValid(self, s: str) -> bool:
valid = dict(zip([')',"]","}"],["(","[","{"]))
s = list(s)
stack = list()
for i in range(len(s)):
if s[i] in valid.values():
stack.append(s[i])
elif stack==[] or valid[s[i]]!=stack.pop():
return False
return not stack
# 76/76 cases passed (28 ms)
# Your runtime beats 92.12 % of python3 submissions
# Your memory usage beats 100 % of python3 submissions (12.8 MB)