20_valid_parentheses_stack.py

"""
Topics:
- stack

O(N), efficient implementation
"""

class Solution:
    def isValid(self, s: str) -> bool:
        close_to_open = {
            "}":"{",
            "]":"[",
            ")":"(",
        }
        stack = []
        for i, char in enumerate(s):
            if char in close_to_open: # if closing char
                # check matches last in stack
                if stack and stack[-1] == close_to_open[char]:
                    stack.pop() # if match, remove from stack
                else:
                    return False # if not match, string invalid because 
                                    # parentheses in wrong order
            else: # if not closing char, add to stack
                stack.append(char)
        # if anything left in stack, False bc parentheses weren't closed
        return True if not stack else False                 

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