Valid Parentheses

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

A string is valid if every opening bracket is closed by the same type of bracket and in the correct order.

Function signature

func IsValidParentheses(s string) bool

Inputs / outputs

• s: string of bracket characters.
• Return: true if valid, else false.

Example

s = "()[]{}" -> true
s = "(]" -> false

Constraints

• 0 <= len(s) <= 100_000

Core idea (near-solution)

Use a stack of opening brackets. When you see a closing bracket, the top of the stack must be the matching opening bracket.

Invariant: the stack always contains unmatched opening brackets in order.

Algorithm (step-by-step)

1. Initialize an empty stack.
2. For each character:
   • If it's an opening bracket, push it.
   • If it's a closing bracket, the stack must be non-empty and the top must match; pop it.
3. At the end, the stack must be empty.

Correctness sketch

• Invariant: the stack always contains unmatched opening brackets in order.
• The stack represents the unmatched structure processed so far.
• Push/pop operations preserve this invariant for each new token.
• At the end, stack emptiness (or top) determines the correct result.

Trace (hand walkthrough)

Example input:
s = "()[]{}" -> true
s = "(]" -> false

Walk:
- "()[]{}": push (, pop with ); push [, pop with ]; push {, pop with } -> empty stack
- "(]": push (, next ] mismatches -> false

Pitfalls to avoid

• Not checking for an empty stack before popping.
• Forgetting to verify the stack is empty at the end.

Complexity

• Time: O(n)
• Extra space: O(n)

Implementation notes (Go)

• Use a slice as a stack of runes.
• Map closing brackets to their expected opening bracket.