Valid Parentheses

s contains only the characters ( ) { } [ ]. It is valid if every opening bracket is closed by the same type of bracket, brackets close in the correct order, and every closing bracket has a matching opener. Return whether s is valid.

Examples

Input:  s = "()[]{}"
Output: true

Input:  s = "(]"
Output: false

Input:  s = "([{}])"
Output: true

Constraints

• 1 ≤ s.length ≤ 10⁴

Explanation

Intuition

The most recently opened bracket must be the first to close — last in, first out. That’s a stack.

Algorithm

• On an opening bracket, push it.
• On a closing bracket, the stack must be non-empty and its top must be the matching opener; pop it. Otherwise return false.
• At the end the stack must be empty (no unclosed openers).

Complexity

• Time: O(n). Space: O(n).