20. Valid Parentheses

Description

See https://leetcode.com/problems/valid-parentheses/

Solution

I had seen this problem before in "A Common-Sense Guide to Data Structures and Algorithms, Second Edition".

I used a deque for the Stack implementation.

class Solution:
    def isValid(self, s: str) -> bool:
        stack = deque()
        close_chars = { ']': '[', 
                        ')': '(', 
                        '}': '{'}
   
        for x in s:
            if x in close_chars:
                if len(stack) <= 0:
                    return False
                else:
                    popped = stack.pop() 
                    if close_chars[x] != popped:
                        return False
            else:
                stack.append(x)
        return len(stack) == 0