Valid Parentheses

Problem Given a string of the characters ()[]{}, determine whether it is valid: every opener is closed by the same bracket type in the correct (LIFO) order.

Input / Output

• Input: string s. Output: boolean.

Constraints

• |s| up to 10^4. Odd length → immediately false.

Example

• "()[]{}" → true; "(]" → false; "([)]" → false; "{[]}" → true.