Stacks and Queues Matching and cancelling
194. Valid Parentheses
You are given a string s made only of the six characters (, ), [, ], { and }. Return true if
its brackets are properly nested, and false otherwise.
The brackets are properly nested when every bracket can be put in a pair, and each pair is an opening bracket followed later by a closing bracket of the same type. Two pairs may sit side by side, or one may sit entirely inside the other, but they may not overlap.
So {[]()} is properly nested: the square pair and the round pair sit side by side inside the curly pair. A
bracket that is never closed, or a closing bracket with nothing open before it, makes the answer false.
Example 1
Input: s = "[{()}](())"
trueExplanation: The round pair sits inside the curly pair, and the curly pair sits inside the square pair. After them, one round pair holds another, so every bracket belongs to a pair.
Example 2
Input: s = "{[}]"
falseExplanation: Each type opens once and closes once, but the [ is still open when the } arrives to close the {.
The square pair and the curly pair overlap.
Example 3
Input: s = ")("
falseExplanation: The string holds one opener and one closer of the same type, but the closer comes first. Nothing is open yet for it to close.
Check your understanding
Work out the answer for this input before you write any code.
Constraints
1 ≤ s.length ≤ 105sholds only the characters(,),[,],{and}.
Clarifying questions
What you would ask an interviewer before writing any code.