Overview
Check if a string of brackets is valid: every opener has a matching closer in the right order.
Analogy
Nesting boxes: each box opened must be closed before closing the outer box.
Step-by-step
- Push opening brackets onto a stack.
- For closing bracket: if stack is empty or top doesn't match, return False.
- Pop the matching opener.
- After processing: stack must be empty.
Visual
'([{}])': push(,[,{; see }: match {, pop; see ]: match [, pop; see ): match (, pop; empty → valid
Common mistakes
- Not checking if stack is empty before popping.
- Forgetting to check stack is empty after processing (unclosed openers).
Practice questions
- Extend to also count the minimum number of swaps to make invalid sequence valid.
- Find the longest valid parenthesis substring.
AI Wisdom