Walkthrough video coming soon
The full explanation is written out below — the problem, the intuition, the approach, and the solution code.
The problem
Given a string `s` containing just the characters `()[]{}`, determine if the input is valid. Brackets must be closed by the same type, and in the correct order.
Constraints & assumptions
- 1 ≤ s.length ≤ 10⁴
- s consists only of the characters '()[]{}'
In plain English
Picture a set of nested gift boxes. The last box you open is the first one you must close — you can't put the lid back on the big box while a smaller box is still open inside it. That strict "last-opened, first-closed" rule is precisely a stack.
Here's the neat trick: every time you open a bracket, drop its matching closer onto the stack. When you meet a closing bracket, it has to match whatever is sitting on top. If it doesn't — or there's nothing on top — the nesting is broken. A valid string leaves the stack empty at the end.
What you need to know
The programming concepts this problem is built on:
How to approach it
- 1Scan the string one character at a time.
- 2When you see an opening bracket, push its matching closing bracket onto a stack.
- 3When you see a closing bracket, the stack's top must equal it — otherwise it's invalid.
- 4At the end, the string is valid only if the stack is empty (nothing left unclosed).
The solutions
2 waysThis one can be solved more than one way. Switch between the methods to compare — each summary explains how it differs.
Push the expected closer; match on the way out. Optimal.
By pushing the closer we expect (rather than the opener itself), every closing character can be checked against the top of the stack in one comparison. One pass, and the empty-stack check at the end handles unclosed brackets.
class Solution {
public boolean isValid(String s) {
Deque<Character> stack = new ArrayDeque<>();
for (char c : s.toCharArray()) {
if (c == '(') stack.push(')');
else if (c == '[') stack.push(']');
else if (c == '{') stack.push('}');
else if (stack.isEmpty() || stack.pop() != c) return false;
}
return stack.isEmpty();
}
}