The example problem
Given a string made of brackets ( ) [ ] { }, decide whether it is valid: every opening bracket must be closed by the same type, in the correct order.
Input: "([]{})"
Output: truePicture it
Picture a stack of plates. Each opening bracket is a plate placed on top. Each closing bracket must match the plate on top: a “]” can only remove a “[” plate. If the top plate is the wrong kind, or there is no plate at all, the string is invalid. At the end the stack must be empty, otherwise something was never closed.
The key idea
Last opened must be first closed, which is exactly what a stack (last in, first out) gives you. O(n).
Python
def is_valid(s):
pairs = {")": "(", "]": "[", "}": "{"}
stack = []
for ch in s:
if ch not in pairs:
stack.append(ch)
elif not stack or stack.pop() != pairs[ch]:
return False
return not stackPractise stack
- LeetCode 84Largest Rectangle in HistogramThe biggest billboard on a skyline
- LeetCode 150Evaluate Reverse Polish NotationA calculator built from plates
- LeetCode 155Min StackPlates with a sticky note for the lightest
- LeetCode 394Decode StringUnwrapping nested gift boxes
- LeetCode 946Validate Stack SequencesCould the plates come off in this order?
NeetCode 150 problems that use it
Stack ·
- LeetCode 20 · EasyValid ParenthesesMatching brackets with a stack of plates
- LeetCode 155 · MediumMin StackPlates with a sticky note for the lightest
- LeetCode 150 · MediumEvaluate Reverse Polish NotationA calculator built from plates
- LeetCode 22 · MediumGenerate ParenthesesStacking cups that open and close
- LeetCode 739 · MediumDaily TemperaturesWaiting for a warmer day
- LeetCode 853 · MediumCar FleetCars bunching into convoys on a one-lane road
- LeetCode 84 · HardLargest Rectangle in HistogramThe biggest billboard on a skyline