Problem

Read the prompt, flip through the examples, then steal the idea.

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.

Constraints

—1 <= s.length <= 10^4
—s consists of parentheses only ()[]{}.

Examples

Input

s =: "()"

Output

true

02

Solution

Python and Go. The walkthrough below runs this same code.

Approach 1Optimal▶ Animated

Stack of open brackets

Push openers; on a closer, the top of the stack must be its matching opener.

Keep a stack of the brackets that are currently open. A closing bracket is only legal if the stack's top is its partner — pop it. Anything else is an immediate false. At the end, the stack must be empty.

A small pairs map (close → open) keeps the code free of a six-way if/elif chain and doubles as the “is this a closing bracket?” test.

Algorithm

Build pairs = { ')': '(', ']': '[', '}': '{' } and an empty stack.
For each character: if it's a closer, the stack must be non-empty and its top must equal pairs[ch] — otherwise return false. Pop.
If it's an opener, push it.
Return true iff the stack is empty at the end.

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

Solution.py

1class Solution:2    def isValid(self, s: str) -> bool:3        pairs = {")": "(", "]": "[", "}": "{"}4        stack: list[str] = []5        for ch in s:6            if ch in pairs:  # closing bracket7                if not stack or stack[-1] != pairs[ch]:8                    return False9                stack.pop()10            else:  # opening bracket11                stack.append(ch)12        return not stack

Watch this run

03

Interactive walkthrough

Playing “Stack of open brackets”. Edit the input, hit Run, then scrub.

Approach: Stack of open brackets

Loading animation…

Valid Parentheses