> For the complete documentation index, see [llms.txt](https://monica-granbois.gitbook.io/cs-theory-and-problems/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://monica-granbois.gitbook.io/cs-theory-and-problems/problems/leetcode/20.-valid-parentheses.md).

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