LeetCode: Valid Parentheses

Determine if a string of parentheses is valid.

Solution

This is a good introduction to LIFO (last-in-first-out) stacks. For this problem, a list is sufficient.

If c is an opening parenthesis, bracket, or brace, add it to the stack.

Otherwise, we need to pop the last item from the stack. If the stack is empty, the string is invalid. If the popped item does not match the current closing character, the string is invalid.

By the end of the string, the stack must be empty.

class Solution:
    def isValid(self, s: str) -> bool:
        stack: List[str] = []
        mapping = {"(": ")", "[": "]", "{": "}"}

        for c in s:
            if c in mapping:
                stack.append(c)
            else:
                if not stack:
                    return False

                last_open = stack.pop()
                if mapping[last_open] != c:
                    return False

        return not stack