# [Valid Parentheses](https://leetcode.com/problems/valid-parentheses/)
###### tags: `Leetcode`, `Easy`, `Stack`

## Approach
* We use a stack
* Map every closing bracket to its opening bracket
* Every time we see an opening bracket, we add it to the stack
* Every time we see a closing brackt, we check if the top element is the corresponding opening bracket

## Asymptotic Analysis
### Time Complexity: **O(N)**
### Space Complexity: **O(N)**

## Code

class ValidParentheses:
    BRACKETS = {
        ']': '[',
        ')': '(',
        '}': '{'
    }

    def is_valid(self, s: str) -> bool:
        stack = []
        for char in s:
            if ((char in self.BRACKETS.keys() and not stack) or
                    (char in self.BRACKETS.keys() and stack and self.BRACKETS[char] != stack.pop())):
                return False
            elif char in self.BRACKETS.values():
                stack.append(char)
        return stack == []


string1, string2, string3 = '}{', '[()]{}', '()]]'
print("Validating parentheses for " + string1 + " : " + str(ValidParentheses().is_valid(string1)))
print("Validating parentheses for " + string2 + " : " + str(ValidParentheses().is_valid(string2)))
print("Validating parentheses for " + string3 + " : " + str(ValidParentheses().is_valid(string3)))