20_valid_parentheses.py

"""
Topics:
- two pointers
"""

class Solution:
    """    
    Inefficient O(N^2) because python string slicing uses a list
    Valid if:
    - Every open bracket is closed by the same type of close bracket.
    - Open brackets are closed in the correct order.
    - Every close bracket has a corresponding open bracket of the same type.

    Ideas
    - recursive function that can go inside each bracket pair and see if there is another bracket pair
    - pointers that find each left brack and look for right one cheking for invalid conditions in between
    - hash map counting each type of bracket 
    - reversed should be equal to ordinay
    
    "(){}[]"
     ^^

     {[]}    
    """
    def isValid(self, s: str) -> bool:
        pairs = {
            ")":"(",
            "}":"{",
            "]":"[",
        }
        if len(s) % 2 != 0: # if string len is odd then invalid
            return False
        
        stack = []
        for char in s:
            if not char in pairs:
                stack.append(char)
            else:
                if not stack:
                    return False
                
                if pairs[char] != stack[-1]:
                    return False
                else:
                    stack.pop()
        return False if stack else True

        
        
            


solution = Solution()
print(solution.isValid("((")) # false
print(solution.isValid("[")) # false
print(solution.isValid("]]")) # false
print(solution.isValid("{[]}")) # true
print(solution.isValid("[(])")) # false
print(solution.isValid("(){}[]")) # true