# Leetcode 20. Valid Parentheses

Description:

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: Use **Stack**
**Time complexity: O(n) (iterate through str)
Space complexity: O(n) (stack could store n-opening parentheses)**

class Solution:
    def isValid(self, s: str) -> bool:
        
        # initialize an empty stack
        stack = []
        
        # create a parentheses hashmap
        mapping = {
            ")": "(",
            "]": "[",
            "}": "{"
        }
        
        # iterate the str
        for c in s:
            # if c is the closing parentheses, peek the stack(and the stack should not be empty)
            if c in mapping:
                if stack and stack[-1] == mapping[c]:
                    # parentheses is matched, pop the opening one
                    stack.pop()
                
                # if c is the opening, we can always push into stack   
                else:
                    stack.append(c)
                    
        # if stack is empty -> all parentheses are matched
        return True if not stack else False