Nesting Gift Boxes
A gift shop packs fragile orders inside layers of packaging: pouches, boxes and crates, nested inside each other in whatever way fits the order. The packer logs every move with one character: ( opens a pouch and ) closes it, [ and ] do the same for a box, { and } for a crate.
A log is fine only if the packer always closed the container they were working in: you cannot seal a crate while a box inside it is still open. Before an order ships, a script checks the log.
Your task
Write packedRight(log). Return true if every container in the log is closed by the matching kind, in the right order, and nothing is left open. Otherwise return false.
A close is correct only if it matches the most recently opened container that is still open. Any kind may sit inside any other kind (a crate inside a pouch is fine); only the order of opening and closing matters. An empty log is fine (nothing was packed), so return true.
packedRight(log: string) → bool
Examples
log = "{[()]}"true
Open crate, open box, open pouch. Then close the pouch, the box and the crate. Each close matches the newest container still open, so the log is fine.
log = "{[}]"false
The packer opens a crate, then a box, then tries to close the crate while the box inside it is still open. Every container is opened and closed once, so a simple count looks fine, but the order is wrong.
log = "[](()"
false
The box opens and closes. Then two pouches open and only one closes. A pouch is left open, so the log is not fine.
Constraints
- 0 ≤ log.length ≤ 10,000
- log contains only the characters ( ) [ ] { }
Start with brute force
Repeatedly delete any adjacent matching pair, (), [] or {}, until no pair is left. If the string ends up empty, the log was fine.
It works, but each pass scans the whole string and may remove only one pair. A log of 10,000 characters can need 5,000 passes over thousands of characters each: tens of millions of steps. A stack does it in one pass.
Hints
0 of 4 shown- Hint 1
In
{[()]}, when the packer types), which container must it close? The first one opened, or the last one? - Hint 2
A close always refers to the newest container that is still open. Once it is closed, the one before it becomes the newest open container again. That is last in, first out.
- Hint 3
Counting openings and closings is not enough:
([)]has one of each kind but is wrong. You need to remember the order the open containers were opened in. - Hint 4
Keep a stack of open containers. On an opening character, push it. On a closing character, the stack must be non-empty and its top must be the matching opener; pop it. At the end, the stack must be empty.
Walkthrough and solution
Unlocks when you pass every test. Stuck for a while? Looking is fine too, as long as you then close it and write the code yourself.
How to solve it
Every close must match the newest container that is still open. "Newest first" is exactly what a stack gives you: push on open, look at the top on close.
Trace {[()]}:
{,[,(: three openings. The stack is{ [ (, with(on top.): the top is(, a match. Pop. Stack:{ [.]: the top is[, a match. Pop. Stack:{.}: the top is{, a match. Pop. The stack is empty and the log is over, so returntrue.
Now {[}]: after {[ the top is [, but the next character is }. That close does not match the top, so return false right away.
Two checks are easy to forget: a close when the stack is empty (] on its own), and openings left on the stack at the end ((().
function packedRight(log) {
const opener = { ')': '(', ']': '[', '}': '{' };
const open = []; // containers still open, newest on top
for (const ch of log) {
if (ch === '(' || ch === '[' || ch === '{') {
open.push(ch);
} else {
// a close must match the newest open container
if (open.length === 0 || open[open.length - 1] !== opener[ch]) return false;
open.pop();
}
}
return open.length === 0; // nothing left open
}def packed_right(log):
opener = {')': '(', ']': '[', '}': '{'}
open_stack = [] # containers still open, newest on top
for ch in log:
if ch in '([{':
open_stack.append(ch)
else:
# a close must match the newest open container
if not open_stack or open_stack[-1] != opener[ch]:
return False
open_stack.pop()
return not open_stack # nothing left openRun your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.