LeetCode 20: Valid Parentheses — Step-by-Step Visual Trace

#leetcode #python #algorithms

Easy — Stack | String | Hash Table

The Problem

Determine if a string containing only parentheses characters is valid, where every opening bracket has a corresponding closing bracket in the correct order.

Approach

Use a stack data structure to track opening brackets. Push opening brackets onto the stack, and when encountering closing brackets, check if they match the most recent opening bracket. The string is valid if the stack is empty at the end.

Time: O(n) · Space: O(n)

Code

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

        for char in s:
            if char in parentheses_map.values():
                stack.append(char)
            elif char in parentheses_map:
                if not stack or stack[-1] != parentheses_map[char]:
                    return False
                stack.pop()
            else:
                return False

        return not stack