### Problem Statement

Given a string

`s`

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. Every close bracket has a corresponding open bracket of the same type.

#### Example 1:

```
Input: s = "()"
Output: true
```

#### Example 2:

```
Input: s = "()[]{}"
Output: true
```

#### Example 3:

```
Input: s = "(]"
Output: false
```

### Solution

#### Intuition & Patterns

Leetcode #20, Valid Parentheses, is a great introduction to `LIFO`

(last in first out) `stack`

problems. The `stack`

data structure can be visualized as a stack of plates at a buffet. The last plate added to the `stack`

will be the first plate removed by a hungry patron.

In **Python**, a `list`

or a double ended queue `deque`

from the `collections`

library will function as a stack. We’ll use `deque`

for this problem. Adding and removing items to stack can be performed in `O(1)`

time.

Let’s say we have the following example string `"{([{}](){})}"`

. We can see that there is inherent symmetry to the problem that reminds us of the parentheses theorem from the DFS (Depth first search) algorithm. In a strange sort of way, this problem serves as an illustration of an iterative implementation of a recursive algorithm. As we loop through each character of the string, an opening `(`

, `[`

, or `{`

represents calling a recursive functions, whereas each closing `)`

, `}`

, or `]`

represents returning from a recursive function.

```
{
(
[
{}
]
()
{}
)
}
```

Building on these observations, we can develop a simple algorithm. For each `closing`

character, check if the top of the stack is the matching `opening`

element. If it is, we pop it from the stack, if not, we add the current character to the stack. Once we loop over the entire string, the `stack`

will be empty if it conformed to the parenthesis theorem, otherwise it will still have element(s) in it.

We can use a `hash table`

to map `closing`

characters to `open`

characters. If we find a match, we `pop()`

from the stack, otherwise we `append(...)`

to it.

#### Python Code

```
from collections import deque
class Solution:
def isValid(self, s: str) -> bool:
stack = deque()
mp = {
")": "(",
"]": "[",
"}": "{"
}
for ch in s:
if stack and stack[-1] == mp.get(ch):
stack.pop()
else:
stack.append(ch)
return False if stack else True
```