You are given a string s that contains only the six bracket characters (, ), [, ], { and }. Return true if every opening bracket is closed by a bracket of the same type, in the correct order. Otherwise return false.
s = "()[]{}" → trues = "(]" → false (a round bracket closed by a square one)s = "([)]" → false (right types, wrong order)s = "{[]}" → true (the square pair sits neatly inside the curly pair)
Look at "([)]". It has one round pair and one square pair, so simple counting says it is fine. But it is not. The [ was opened after the (, so it must be closed before the (. Here the ) arrives while the [ is still open.
That shows the real rule. A closing bracket must always match the most recently opened bracket that is still waiting to be closed. "Most recent first" is the key phrase.
A structure that always hands back the most recent item first is a stack. A stack is like a pile of plates. You can only add a plate to the top, and you can only take the top plate off. The last plate you put on is the first one you take off. This is called last in, first out.
One slow idea is to keep deleting matched pairs that sit side by side, like (), [] or {}, until nothing changes.
python
def isValid(s): while "()" in s or "[]" in s or "{}" in s: s = s.replace("()", "").replace("[]", "").replace("{}", "") return s == ""
On "{[]}", the first round deletes [] to give "{}", and the second deletes that to give "". Correct. But each round scans and rebuilds the whole string, and a deeply nested string like "(((...)))" needs about n/2 rounds. That is O(n^2).
The waste in one sentence: each round rescans the whole string to find the innermost pair, when a stack always knows which bracket is innermost.
When you see an opening bracket, push it onto the stack. It is now waiting to be closed.
When you see a closing bracket, the top of the stack must be its partner. Pop it and check. If the stack is empty, or the top is the wrong type, the string is invalid.
At the end, the stack must be empty. Anything left was opened and never closed.
class Solution: def isValid(self, s: str) -> bool: pairs = {')': '(', ']': '[', '}': '{'} # (1) stack = [] # (2) for c in s: # (3) if c in pairs: # (4) if not stack or stack.pop() != pairs[c]: # (5) return False else: # (6) stack.append(c) return not stack # (7)
ts
function isValid(s: string): boolean { const pairs: Record<string, string> = { ')': '(', ']': '[', '}': '{' }; // (1) const stack: string[] = []; // (2) for (const c of s) { // (3) if (c in pairs) { // (4) if (stack.pop() !== pairs[c]) return false; // (5) } else { // (6) stack.push(c); } } return stack.length === 0; // (7)}
(1) A map from each closing bracket to its opening partner. It is keyed by the closing bracket because that is the direction we look things up. When we meet ), we want to know what should be on top of the stack, and the map tells us: (.
(2) The stack. A plain list works as a stack. append puts an item on top, and pop takes the top item off and returns it.
(3) Walk the string once, one character at a time.
(4) Is this a closing bracket?c in pairs checks whether c is one of the map's keys, which are exactly the three closing brackets.
(5) Check the top of the stack. Two things can go wrong, and this line catches both.
The stack is empty. A closer has nothing to close, as in ")". In Python, pop() on an empty list raises an error, so not stack must be checked first. Python's or stops as soon as the left side is true, so the pop never runs on an empty stack. In JavaScript, pop() on an empty array just returns undefined, which never equals a bracket, so the comparison alone catches it.
The top is the wrong type, as in "(]". The popped ( does not equal [, the partner of ].
Either way, the string is invalid.
(6) An opening bracket. Push it. It now waits for its partner.
(7) The stack must be empty at the end.not stack is True when the list is empty. Anything left over was opened and never closed, as in "(((". Forgetting this check is the most common bug here, and it passes most small examples.
Time. We visit each of the n characters once. Each visit does one map lookup and at most one push or pop, all constant time. So the time is O(n).
Space. In the worst case every character is an opener, like "((((((", and all of them end up on the stack. So the stack can hold n items, which is O(n).
Only closers, like ")". The stack is empty when the closer arrives, so line (5) returns false.
Only openers, like "((". Nothing is ever popped, so line (7) returns false.
Odd length. A string with an odd number of characters can never be valid, because brackets come in pairs. You can return false at the start with if len(s) % 2: return False. It is a small shortcut, not required.
Deep nesting, like "((((()))))". The stack grows to half the length, then empties.
Nesting is everywhere, and wherever it appears, the answer is a stack.
Reading code. Every programming language has blocks inside blocks. The part of a compiler that reads your code checks its brackets exactly like this, with a much bigger set of "brackets". Part 3 covers how that works.
The call stack. When a function calls another function, the computer pushes a note of where to come back to. When that function returns, the note is popped. A call is an opener, and a return is its closer.
Undo. The most recent action is the first one undone.
If you can see nesting in a problem, you have already chosen your data structure.
Longest Valid Parentheses. Find the longest balanced stretch inside a string of ( and ). You push positions instead of brackets, with a starting marker at the bottom of the stack to measure lengths against.
Minimum Add to Make Parentheses Valid. With only one bracket type, you do not need a stack at all. Two counters are enough: how many ( are open, and how many unmatched ) you have seen.
Generate Parentheses. Build every valid string, instead of checking one. That is 4.8.4.
The general lesson: when the most recently opened thing must be closed first, use a stack.
"Why not just count each bracket type?" Counting misses order. "([)]" has balanced counts but is invalid.
"What are the three ways the string can fail?" A closer with an empty stack, a closer that does not match the top, and openers left at the end. Naming all three shows you thought about it.
"What if there were only round brackets?" Then one counter is enough. Add 1 for (, subtract 1 for ), fail if it ever goes below zero, and require zero at the end.
"What if the string also contains letters?" Skip anything that is not a bracket. The stack logic does not change.
One thing to volunteer: point out that the map is keyed by the closing bracket on purpose, because that is the direction you look things up when a closer arrives.
Next:4.8.2 Min Stack. A stack that can also tell you its smallest value instantly.