Given a string s containing only the characters (){}[], determine whether it's valid — every opening bracket must be closed by the same type of bracket, and closed in the correct order.
Example
Input s = "()[]{}"
Output true
Key Pointers
A stack fits naturally because the most recently opened bracket must be the next one closed — last in, first out.
Push opening brackets; on a closing bracket, check it matches the top of the stack.
The string is valid only if the stack ends empty — leftover unmatched opens, or a closer with nothing to match, both mean invalid.
Step-by-Step Analysis
Create an empty stack and a mapping from each closing bracket to its matching opening bracket.
For each character: if it's an opening bracket, push it onto the stack.
If it's a closing bracket, check the stack isn't empty and its top matches the expected opening bracket — pop if so, otherwise return False immediately.
After processing every character, return True only if the stack is empty.
Complexity
Time: O(n) — Space: O(n)
Code
def isValid(s: str) -> bool:
pairs = {")": "(", "]": "[", "}": "{"}
stack = []
for ch in s:
if ch in pairs:
if not stack or stack[-1] != pairs[ch]:
return False
stack.pop()
else:
stack.append(ch)
return not stack
Code Explanation
How the solution above works, piece by piece.
pairs maps each closing bracket to the opening bracket it needs.
An opening bracket is pushed: it waits for its partner.
A closing bracket must match the most recent unmatched opener, which is exactly the top of the stack. If the stack is empty or the top is the wrong type, the string is invalid.
On a match, pop the opener; that pair is done.
return not stack: leftover openers were never closed. One pass: O(n) time and O(n) stack space.
Visual Walkthrough
Running it on s = "()[]{}":
Openers are pushed; each closer must match the opener on top of the stack, which is popped. The stack ends empty, so the string is valid.