# Problem

Given a string s 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.
3. 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

We must start with an opening bracket, if we start with a closing bracket no matter what we do we cannot fix it.

We can add as many open brackets as we want, so long as they eventually close.

As soon as we find 2 matching brackets we can remove them from our stack.

A Cleaner code would be:

class Solution:
def isValid(self, s: str) -> bool:
stack = []
closeToOpen = {"]":"[", "}":"{", ")":"("}

for c in s:
# if its a closing brace
if c in closeToOpen:
# We cannot have a closing brace and empty stack
# as that would mean theres no opening braces
# If the most recently added item to our stack is the opening brace of the thing we are tring to close
if stack and stack[-1] == closeToOpen[c]:
# remove the opening brace and do not append the closing brace as they are a pair
stack.pop()
else:
# else either the stack is empty or we have a closing brace with no opening, returning false
return False
else:
# else its an opening brace. We can add as many opening braces as we want so long as we eventually close them
stack.append(c)
# if the stack is empty that means every opening brace has a closing brace
# else if the stack is not empty, this was not true so we must fail
return True if not stack else False