The stack was empty and pop() returned None, and the comparison against Some(’(’) caught that too.
A closing bracket has two ways to be wrong. The stack can be empty, so there is nothing to match it against, or the stack can have the wrong kind of opener on top. Most solutions check those separately.
This one does not:
if stack.pop() != Some('(') {
return false;
}
That single comparison covers both. stack.pop() returns Option<char>, and Option<char> compares against Option<char>. When the stack is empty the pop declines and returns None, and None != Some(’(’) is true, so the function returns false without a separate emptiness check. When the stack has ’[’ on top, the pop succeeds and returns Some(’[’]), and Some(’[’]) != Some(’(’) is also true. Same branch, same outcome, no second condition.
I checked the empty case directly, because the whole argument rests on None != Some(’(’) being true rather than somehow panicking:
empty.pop() != Some('(') -> true
empty.pop() == None -> true
['.pop() != Some('(') -> true
The stack refuses to pop, and the comparison refuses to accept what it got back. The function does not need to know which happened.
The function in full
pub fn is_valid(s: String) -> bool {
let mut stack = vec![];
for ch in s.chars() {
match ch {
'(' | '[' | '{' => stack.push(ch),
')' => {
if stack.pop() != Some('(') {
return false;
}
}
']' => {
if stack.pop() != Some('[') {
return false;
}
}
'}' => {
if stack.pop() != Some('{') {
return false;
}
}
_ => {}
}
}
stack.is_empty()
}
Three arms do the same thing with a different expected opener, and the _ => {} arm drops anything that is not a bracket. The problem statement says the string contains only brackets, so that arm is unreachable in practice, but it has to exist because the compiler does not know what is in the string.
The last line handles the other half of validity. A string like "(((" never fails inside the loop, because every character is an opener and nothing is ever compared. The unfinished openers are caught at the end by stack.is_empty().
I ran the function over a spread of inputs and got the expected answers:
"()" -> true
"()[]{}" -> true
"(]" -> false
"([])" -> true
"([)]" -> false
")" -> false
"(((" -> false
"([{}])" -> true
Two constants nothing reads
At the top of the same file:
const OPENING: [char; 3] = ['(', '[', '{'];
const CLOSING: [char; 3] = [')', ']', '}'];
Nothing in the function reads either one. The match arms hardcode the characters, and the expected opener is written into each comparison by hand. These two constants are the remains of a design where the opener for a given closer was looked up rather than spelled out.
They are also why the file starts with this:
#![allow(unused)]
I removed that attribute and rebuilt the file. The compiler emitted exactly two extra warnings, both under #[warn(dead_code)] and both noting that the lint is part of #[warn(unused)]:
warning: constant `OPENING` is never used
warning: constant `CLOSING` is never used
To be precise about what the attribute is doing across this repo: all six answer crates need #![allow(unused)] because struct Solution is never constructed in a binary whose entry point is fn main(). The harness that grades these calls the method; the crate as committed does not. The two dead constants make 020 the only one of the six that also has to suppress dead_code.
The arm won
The match arm and the constants are two answers to the same question. The arm says: for each closer, here is the opener it must match. The constants say: here are the openers and the closers as sets.
The arm won. Once the opener is written into the comparison, the sets are redundant, because the code never has to ask what the set contains. But the constants are still there, and the allow attribute is what kept them from being noise on every build.
That is a small thing, and it is the kind of thing that piles up. A file that needs #![allow(unused)] at the top has stopped telling you what is going on. The attribute says: do not tell me about the parts I have not looked at. In this crate it covers a struct the harness will use and two arrays that nothing will ever read.
The comparison is the part worth keeping, because it is where the two failure modes collapse into one.
What I do with that file now is read the top of it first. An #![allow(...)] line is a note to my future self, and my future self does not remember writing it. The compiler was willing to tell me about the struct and the two arrays on every build, and the attribute is what stopped it.
Next: Allocating Once