Leetcode - 20. Valid Parentheses

Easy

Dec 22, 2025

#stack

20. Valid Parentheses

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.
Every close bracket has a corresponding open bracket of the same type.

Example 1:

Input: s = "()"

Output: true

Example 2:

Input: s = "()[]{}"

Output: true

Example 3:

Input: s = "(]"

Output: false

Example 4:

Input: s = "([])"

Output: true

Example 5:

Input: s = "([)]"

Output: false

1 <= s.length <= 104
s consists of parentheses only '()[]{}'.

Constraints:

Notes

Intuition

Brackets must close in the reverse order they were opened. A stack naturally enforces this LIFO property—each closing bracket should match the most recently opened one.

Implementation

Use a map from opening to closing brackets. When encountering an opening bracket, push its expected closing bracket to the stack. When encountering a closing bracket, check if it matches the stack top—if so, pop and continue; if not (or stack is empty), return False.

Edge-cases

Two important checks: the stack must be empty at the end (no unclosed brackets), and encountering a closing bracket when the stack is empty means there's no matching opener.

Time: O(n) — single pass through the string
Space: O(n) — stack can hold up to n/2 brackets

Complexity

Solution

class Solution:
    def isValid(self, s: str) -> bool:
        map = {
            "(": ")",
            "{": "}",
            "[": ']',
        }
        stack = []
        for c in s:
            if c in map:
                # opening bracket
                stack.append(map[c])
            else:
                if len(stack) == 0 or stack[-1] != c:
                    return False
                stack.pop()


        return len(stack) == 0
        



if __name__ == "__main__":
    # Include one-off tests here or debugging logic that can be run by running this file
    # e.g. print(solution.two_sum([1, 2, 3, 4], 3))
    solution = Solution()