Valid Parentheses

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.

Example:

• Input: s = "()[]{}" -> Output: true
• Input: s = "(]" -> Output: false
• Input: s = "([)]" -> Output: false

We use a Stack data structure.

1. Iterate through the string char by char.
2. If we see an open bracket ((, {, [), push it onto the stack.
3. If we see a close bracket (), }, ]), check the top of the stack:
   • If stack is empty, it's invalid (no matching open).
   • If stack top is the matching open bracket, pop the stack.
   • Otherwise, it's a mismatch -> invalid.
4. At the end, stack must be empty (all opened brackets were closed).

Watch how the stack grows with open brackets and shrinks with matching closed ones.