# 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](https://pragprog.com/titles/jwdsal2/a-common-sense-guide-to-data-structures-and-algorithms-second-edition/)".&#x20;

I used a deque for the Stack implementation.

```python
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
```