Stacks & Queues/Practice/Valid Parentheses
Valid Parentheses - Explained Step by Step
Scan the string once with a stack. An opening bracket goes on the stack. A closing bracket must match whatever is on top - if it does, pop it; if it does not (or the stack is empty), the string is invalid. Valid only if the stack ends empty.
Why it works
Brackets close in the reverse order they opened, which is exactly last-in-first-out - the definition of a stack. The most recently opened bracket is always the next one that must close, so one stack pass is O(n) time and O(n) worst-case space.
The problem
Given a string containing just the characters (, ), {, }, [, ], determine if the input string is valid. Open brackets must be closed by the same type and in the correct order.
Hints
- Push opening brackets onto the stack.
- For closing brackets, check if the top of the stack is the matching opener.
- At the end, the stack should be empty for a valid string.
Test cases
| Input | Expected |
|---|---|
is_valid("()") | True |
is_valid("()[]{}") | True |
is_valid("(]") | False |
is_valid("([)]") | False |
Reference starter code
def is_valid(s):
# Use a stack
pass
print(is_valid("()")) # True
print(is_valid("()[]{}")) # True
print(is_valid("(]")) # False
print(is_valid("([)]")) # False
print(is_valid("{[]}")) # True
More challenges in this topic
Try it yourself
Solve it in the browser editor with real test cases and instant feedback - free, no signup needed.
Next challenge in this topic: Daily Temperatures