Valid parentheses

easyStack target 15 min

Valid parentheses

Not solved yetLeetCode 20. Valid Parentheses

The string s is made only of the bracket characters (, ), [, ], { and }. Return True if its brackets are matched, and False if they are not.

Matched means this. Read s from left to right. Each closing bracket must close the most recent opening bracket that is still open, and the two must be the same kind: ( with ), [ with ], { with }. A closing bracket that arrives with nothing open breaks the rule. When the string ends, no opening bracket may still be open.

So ([)] is not matched, even though each kind opens once and closes once. The empty string has nothing to close, so it is matched.

Example 1

Inputs = "([]{})"OutputTrue

The [] and the {} each close inside the ( ), and the ) closes last.

Example 2

Inputs = "([)]"OutputFalse

The ) arrives while [ is the most recent bracket still open.

Example 3

Inputs = "{[]"OutputFalse

The [] matches, but the { is never closed.

Constraints

0 ≤ len(s) ≤ 2 × 10⁵
Every character is one of ( ) [ ] { }.

Plan it first

Write a line for each before you code, then say them out loud. Compare with the Approach tab afterwards.

Walk In what order will you visit the input?Notebook What will you write down as you go?Promise What stays true after every step?Cost Time and space, in Big O.

Run examples checks the examples. Submit runs every test, including edge cases and, when the problem has one, a speed check on a large input.

Same pattern