### 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.

``````{
(
[
{}
]
()
{}
)
}
``````
flowchart TD a["{ ... }"]-->b["( ... )"] b-->c["[ ... ]"] c-->d[" { }"] b-->e["( )"] b-->f["{ }"]

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
``````

Leetcode 20 Valid Parentheses