Given a string s made only of the characters (, ), {, }, [ and ], decide whether it is valid. It is valid when every opening bracket is closed by a bracket of the same type, brackets are closed in the correct order, and every closing bracket has a matching opening bracket before it.
[ is still open when ) arrives, so the order is wrong.- 1 <= s.length <= 10^4
- `s` contains only the six bracket characters
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
A brute force repeatedly deletes adjacent pairs like (), [] and {} until nothing changes, which is O(n^2). The pattern "the last opened must be the first closed" is exactly what a stack models. Every opening bracket waits on the stack; a closing bracket must match the top, otherwise the string is invalid. If anything is left on the stack at the end, some bracket was never closed.
Algorithm
- Create an empty stack and a map from each closing bracket to its opening bracket.
- For each character: if it is an opening bracket, push it.
- If it is a closing bracket, return false when the stack is empty or its top is not the matching opener; otherwise pop.
- After the loop, return true only if the stack is empty.
O(n)Space: O(n)"((" (check the stack is empty at the end). A quick early exit: an odd length can never be valid.class Solution: def isValid(self, s: str) -> bool: pairs = {')': '(', ']': '[', '}': '{'} stack = [] for c in s: if c in pairs: # closing bracket: the top must be its partner if not stack or stack[-1] != pairs[c]: return False stack.pop() else: stack.append(c) return not stack # every opener must be closed