Valid Parentheses

Problem

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

1. Open brackets must be closed by the same type of brackets.
2. Open brackets must be closed in the correct order.
3. Every close bracket has a corresponding open bracket of the same type.

Input / Output Format

Input: Bracket-only string s. Output: Boolean.

Examples

Example 1

Input: s = "()" → Output: true

Example 2

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

Example 3

Input: s = "(]" → Output: false

Approach Hints

• Use a stack. Iterate chars. If opener, push. If closer, pop and verify pair. If pop on empty stack or mismatch → false.
• After scan, valid iff stack empty.
• Use a map {')':'(', ']':'[', '}':'{'} for clean code.
• Time: O(n). Space: O(n) worst case.