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: Every opening bracket should eventually have a closing bracket that comes after it.
Implementation: Use a stack and a map that maps opening brackets to closing, when seeing an opening bracket, push the closing bracket to the stack, When seeing a closing bracket, check the top of the stack, if its the same, pop and keep going, otherwise return False.
Edge-cases: At the end, check the stack should be empty (unclosed brackets at the end). Also check if the stack is empty on seeing a closing bracket, return False there was no corresponding open.
Complexity: Time O(n), Space O(n) (stack)

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()