Problem overview
The function is_valid receives a string, input, made only of the characters (, ), {, }, [ and ]. It returns true when the brackets are balanced and false otherwise. Two rules define balanced:
- every opening bracket is closed by a bracket of the same type;
- brackets close in the right order: the most recently opened one is closed first.
"()", "()[]{}" and "{[]}" are valid. "(]" is not, because the type is wrong, and "([)]" is not, because the [ is still open when the ) tries to close the ( underneath it.
The statement asks for O(n) time and O(n) extra space.
Approach: a stack of open brackets
Counting brackets is not enough. In "([)]" every bracket has a partner of the same type, yet the string is invalid, because the order is wrong. What matters is that a closing bracket must match the most recent opening bracket that is still open. "Most recent first" describes a stack.
Scan the string from left to right:
- An opening bracket is pushed onto the stack. It waits there until its closing bracket arrives.
- A closing bracket must match the top of the stack. Pop the top, and compare. If the stack is empty, or the popped bracket is of another type, the string is invalid.
At the end, the stack must be empty. Anything left on it is an opening bracket that was never closed, as in "((".
A map from each opening bracket to its closing partner keeps the matching rule in one place, so the loop does not need a separate branch for each of the three types.
Take "([)]". The ( and the [ are pushed, so the stack is ( then [. The ) pops the [. The partner of [ is ], not ), so the function returns false on the third character.
Step by step
- Build the map
closingfrom each opening bracket to its closing one, as aHashMap<char, char>. It is built from an array of pairs with.iter(),.cloned()and.collect().iter()yields references to the pairs,cloned()copies each pair, andcollectbuilds the map named by the type annotation. - Create the stack as an empty, mutable
Vec<char>. Its last element is the top. - Loop over the characters of
inputwithinput.chars(), calling each onebracket. - Test for an opening bracket.
closing.contains_key(&bracket)is true exactly whenbracketis a key of the map, which means it is an opening bracket. The method takes a reference. - Push it. An opening bracket goes onto the stack.
- Handle everything else in an
elsebranch. What isn't a key must be a closing bracket. - Pop and match. Inside the
else,matchonstack.pop(), which is anOption<char>. TheNonearm,None => return false, covers a closing bracket with nothing open. - Bind the popped bracket. The
Some(open)arm names the bracket taken from the stack: the only one this closing bracket may close. - Compare with its partner. If
bracketis notclosing[&open], the type is wrong, and the function returnsfalse. - Check that nothing is left open. After the loop,
stack.is_empty()is the final expression. It istrueonly when every opening bracket was closed.
The solution in Rust
use std::collections::HashMap;
impl Solution {
fn is_valid(input: String) -> bool {
let closing: HashMap<char, char> = [('(', ')'), ('{', '}'), ('[', ']')]
.iter()
.cloned()
.collect();
let mut stack: Vec<char> = Vec::new();
for bracket in input.chars() {
if closing.contains_key(&bracket) {
stack.push(bracket);
} else {
match stack.pop() {
Some(open) => {
if bracket != closing[&open] {
return false;
}
}
None => return false,
}
}
}
stack.is_empty()
}
}
The Rust details worth a closer look:
- Characters, not bytes.
input.chars()yieldscharvalues. AStringcan't be indexed withinput[i], because it is UTF-8 and indexing by position isn't defined. Iterating overchars()is the normal way to read it. The brackets here are single-byte ASCII, butchars()is the habit that works for any text. - Collecting into a map. An iterator of
(char, char)pairs can be collected into aHashMap, using the first element as the key and the second as the value. The type annotation onclosingtellscollectwhat to build. Without.cloned(), the iterator would yield&(char, char), which can't be collected into this map. - Indexing a map.
closing[&open]panics if the key is missing. It is safe here, because only keys of the map are ever pushed onto the stack.closing.get(&open)would return anOptioninstead. - Exhaustive
match. Amatchmust cover every case.Optionhas two,SomeandNone, and the code has an arm for each. TheSomearm has a block as its body, and theNonearm is a single expression,return false. The block's value is(), andreturn falsehas a type that fits any arm, so the two arms agree. - Early return.
return falseleaves the function at once from inside the loop and thematch. The last line has no semicolon, so it is the value returned when the loop completes.
Complexity
Time: O(n). The loop looks at each character once. A map lookup, a push and a pop each take constant time (the map has three entries, and a push is O(1) amortized).
Space: O(n). In the worst case, such as a string of only opening brackets, the stack holds every character. The map has three entries, which is a constant.
Edge cases and common mistakes
- Closing bracket first.
")"and"]["hit the empty stack and returnfalsethrough theNonearm. - Unclosed openers.
"(("and"(()"pass through the loop, and the finalstack.is_empty()reportsfalse. Returningtrueat the end without that test would be wrong. - Extra closers.
"())"returnsfalseat the third character, because the stack is empty again by then. - Right count, wrong order.
"([)]"is rejected because the top of the stack is the wrong type. - Nesting.
"{[()]}"is valid: each closer meets its own opener at the top. - Only counting. Checking that the number of
(equals the number of), and the same for the others, accepts"([)]". - Empty string. The function returns
true, since the loop doesn't run and the empty stack counts as balanced. The constraints say the string has at least one character.
Testing
"()"givestrue."()[]{}"givestrue."{[()]}"givestrue."(]"givesfalse."([)]"givesfalse."(()"givesfalse."())"givesfalse.
