Developers

Valid Parentheses

EasyStackGrade AAlso known as LeetCode 20

You get a string made only of these six characters: ( ) [ ] { }.

Return true if every opening bracket is closed by a bracket of the same kind, and the brackets close in the correct order. Otherwise return false.

An empty string counts as valid.

Examples

Input s = "([]{})"
Output true
Each bracket closes the one opened most recently.
Input s = "([)]"
Output false
The square bracket was opened after the round one, so it has to close first.
Input s = "((("
Output false
Brackets were opened and never closed.

Constraints

  • 0 <= s.length <= 10,000
  • s contains only ( ) [ ] { }

Stuck? Take one hint at a time

Common mistakes
  • Forgetting to check that the stack is empty at the end.
  • Popping from an empty stack when a closing bracket comes first.
  • Only counting brackets of each kind, which wrongly accepts "([)]".
  • Comparing the closer with the top without translating it to its opener first.
Questions an interviewer may ask next
  • Return the position of the first bracket that breaks the rule.
  • With only one kind of bracket, can you do it in constant space? (A counter is enough.)
  • Find the fewest brackets to remove so the string becomes valid.
  • The string arrives as a stream. What state must you keep?

How often this is reported

Commonly reported across 16 of 25 tracked companies
16/25

Grade A: Reported in several independent candidate sources. This reflects what candidates report, not a guarantee of what any company will ask.