ASAPUtils
The signal
Pairs must be matched and correctly nested. Nested work finishes inside-out: the newest opener must close first. That is exactly LIFO order.
Approach ladder
1. Count each bracket type — wrong
Counts say ([)] has the right number of each symbol. They cannot tell that [ was still open
when ) arrived. This is an order problem, not only a frequency problem.
2. Repeatedly remove (), [], {} — O(n²)
It can work, but each replacement scans and rebuilds the string. The stack represents the same inside-out removal in one pass.
3. Stack of unmatched openers — O(n)
bool isValid(string s) {
unordered_map<char,char> close = {{')','('}, {']','['}, {'}','{'}};
vector<char> st;
for (char c : s) {
if (!close.count(c)) {
st.push_back(c);
} else {
if (st.empty() || st.back() != close[c]) return false;
st.pop_back();
}
}
return st.empty();
}
function isValid(s) {
const close = { ')': '(', ']': '[', '}': '{' };
const stack = [];
for (const c of s) {
if (!(c in close)) {
stack.push(c);
} else {
if (stack.at(-1) !== close[c]) return false;
stack.pop();
}
}
return stack.length === 0;
}
The invariant
Before reading each character, the stack contains exactly the open groups not yet closed, in the order they opened. Its top is the innermost unfinished group. A closer for anything else proves the nesting is wrong immediately.
Complexity
- Time O(n): each character is read once and pushed or popped at most once.
- Space O(n): all characters could be openers.
Traps
- Calling
back()before checking an empty C++ stack. - Returning true immediately after the loop without checking leftover openers.
- Using counts, which lose ordering information.
- Putting closer characters on the stack too. Store only unfinished work: the openers.
Blank re-solve prompt
Validate three bracket types in one pass. State the stack invariant before writing code.