Valid Parentheses in Python
Learn how to solve the Valid Parentheses problem using a Stack in Python! A super fun and easy tutorial on matching brackets for technical interviews.
Try it yourself
Run this code directly in your browser. Click "Open in full editor" to experiment further.
Click Run to see output
Or press Ctrl + Enter
How it works
The Valid Parentheses problem is an absolute classic! It simply asks: Is every single opening bracket properly closed in the exact correct order?
Valid examples: ()[]{} or [{()}]
Invalid examples: ([)] or (((
The Magic of Stacks
This problem is absolutely tailor-made for a Stack data structure! A stack works just like a stack of pancakes (Last-In, First-Out). You can only add or remove from the very top.
How It Works
1. We walk through the string of brackets one character at a time.
2. If we see an OPENING bracket ((, {, or [): We just toss it onto the top of our pancake stack!
3. If we see a CLOSING bracket (), }, or ]):
- Uh oh, what if the stack is completely empty? That means we have a closing bracket with NO opening bracket! That's instantly Invalid.
- If the stack isn't empty, we pop the top bracket off and check it. Does it match? If we pulled a [ but our current closing bracket is a }, that's a mismatch! Invalid.
4. The Final Check: Once we've checked the entire string, what if we have extra opening brackets sitting on our stack that were never closed? The stack MUST be perfectly empty at the end for the string to be Valid!
Time and Space Complexity
((((((( ), we have to put every single character onto our stack memory.Pro Tip 💡
Whenever you see a coding problem that involves matching pairs, nested structures, or an undo button, try using a Stack!
