Valid Parentheses

The problem description can be found in LeetCode.

Approach

This is a classic problem to use a Stack. The idea is also quite intuitive.

Every time we see an open parenthesis, we can push the corresponding closed one in the stack. On the other hand, if the current parenthesis is a closed one, we check the top of the stack and if it is empty or it does not correspond, the string is not valid; otherwise, we continue with the next character.

Solution

class Solution:
    def isValid(self, s: str) -> bool:
        m = {
            "}": "{",
            "]": "[",
            ")": "(",
        }
        open_pars = set(m.values())

        stack = []
        for char in s:
            if char in open_pars:
                stack.append(char)
            else:
                if not stack:
                    return False
                if stack.pop() != m[char]:
                    return False

        return len(stack) == 0

Complexity

• Time: $O(n)$
• Space: $O(n)$

Where $n$ is the size of the s list.