Leetcode 0020. Valid Parentheses

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

This is very classical problem for using stacks, for me it was literally the first problem I saw on this topic. If you know that you need to use stack here, it becomes nice and easy.

What is valid parentheses? It is when we meet some close bracket, it means that we need to find corresponding open bracked of the same type. We traverse our s and if we:

1. see open bracket we put it to stack
2. see closed bracket, then it must be equal to bracket in the top of our stack, so we check it and if it is true, we remove this pair of brackets.
3. In the end, if and only if we have empty stack, we have valid string.

Complexity: time complexity is O(n): we put and pop each element of string from our stack only once. Space complexity is O(n).

class Solution:
    def isValid(self, s):
        dct = {"[": "]", "(": ")", "{" : "}"}
        stack = []
        for char in s:
            if char in dct:
                stack.append(char)
            else:
                if not stack or char != dct[stack.pop()]: return False           
        return not stack

If you like the solution, you can upvote it on leetcode discussion section: Problem 0020