Problem overview
The function group_anagrams receives a vector of strings and returns them grouped so that every group holds words made of exactly the same letters. The groups can come back in any order.
For ["eat", "tea", "tan", "ate", "nat", "bat"] the groups are ["eat", "tea", "ate"], ["tan", "nat"] and ["bat"]. Inside a group the words keep their input order, but the order of the groups is not fixed.
With n words of length at most L, the statement asks for O(n * L * log L) time and O(n * L) extra space.
Approach: a canonical key for every word
Comparing every pair of words to see whether they are anagrams would cost at least O(n²) comparisons. A better idea gives each word a key that is identical for all of its anagrams and different for everything else. Then grouping is just a matter of putting words with the same key together in a hash map.
The simplest key is the word with its letters sorted. "eat", "tea" and "ate" all become "aet"; "tan" and "nat" become "ant"; "bat" becomes "abt". Two words are anagrams exactly when their sorted forms are equal, because sorting throws away the order and keeps the multiset of letters.
Sorting one word of length L costs O(L log L), and doing it for n words gives the O(n * L * log L) in the statement. The map operations are cheap on average: hashing a key of length L costs O(L).
Step by step
- Create the map.
group_by_sortedis an empty, mutableHashMapfrom the sorted form (aString) to the list of words that share it (aVec<String>). - Loop over
stringsby value. Eachsis then an ownedStringthat can be moved into its group later, with no cloning. - Collect the characters of
sinto a mutableVec<char>calledchars. AStringcan't be sorted in place, but a vector of characters can. - Sort
charsso the letters are in ascending order. - Turn the sorted characters back into a
Stringnamedsorted_string. This is the key shared by all anagrams ofs. - Add
sto its group.entry(sorted_string)looks the key up,or_insert_with(Vec::new)creates an empty vector when the key is new, andpush(s)appends the word to whatever vector is now in the map. - Return the groups.
into_values()consumes the map and yields the vectors, andcollect()gathers them into the returnedVec<Vec<String>>.
The solution in Rust
use std::collections::HashMap;
impl Solution {
fn group_anagrams(strings: Vec<String>) -> Vec<Vec<String>> {
let mut group_by_sorted: HashMap<String, Vec<String>> = HashMap::new();
for s in strings {
let mut chars: Vec<char> = s.chars().collect();
chars.sort();
let sorted_string: String = chars.iter().collect();
group_by_sorted
.entry(sorted_string)
.or_insert_with(Vec::new)
.push(s);
}
group_by_sorted.into_values().collect()
}
}
The Rust details worth a closer look:
- Why the characters go into a vector. Strings in Rust are UTF-8 bytes, and they can't be indexed or sorted in place.
s.chars()yieldscharvalues (Unicode scalar values), and collecting them into aVec<char>gives somethingsort()can reorder. Characters sort by their code point, so"aBc"sorts to['B', 'a', 'c']: uppercase letters come before lowercase ones. That doesn't affect grouping, because every anagram is sorted the same way. collectfollows the annotation again.chars.iter()yields&char, and aStringcan be built from an iterator of those. The: Stringannotation onsorted_stringis what asks for it.- Ownership.
entry(sorted_string)moves the key into the map. The key was built from a copy of the word's characters, sositself is still available, andpush(s)moves it into the group. The loop overstringsby value is what makes that move possible. - The entry API.
or_insert_with(Vec::new)runsVec::newonly when the key is missing, and returns a&mut Vec<String>to the value in the map either way. That is whypushcan be chained directly, and why the map is looked up once instead of twice. - Output order. A
HashMaphas no defined iteration order, and Rust randomises its hashing, sointo_values()can return the groups in a different order from one run to the next.
Complexity
Time: O(n * L * log L). For each of the n words, collecting the characters is O(L), sorting them is O(L log L), building the key is O(L), and the map insertion is O(L) on average because the key has to be hashed and compared. The sort dominates.
Space: O(n * L). The map stores one sorted key per distinct group, plus every word exactly once. The temporary vector of characters holds only one word at a time.
Edge cases and common mistakes
- Empty input. An empty vector gives an empty vector of groups.
- Empty strings. Their sorted form is the empty string, so all of them land in one group: two
""words return[["", ""]]. - A single word. It forms a group of its own.
- Repeated words. Identical words are anagrams of each other and share a group, once per occurrence.
- Different letter counts. "aab" and "ab" must not match. Sorting keeps repeated letters, so their keys, "aab" and "ab", differ.
- Using the original word as the key. The map would then have one entry per word and no grouping would happen.
- Comparing the output with
==against an expected list. Since the group order isn't fixed, sort the groups (and the words inside them) first when you test.
Testing
["eat", "tea", "tan", "ate", "nat", "bat"]gives three groups:["bat"],["tan", "nat"]and["eat", "tea", "ate"], in any order.["a"]gives[["a"]].["", ""]gives[["", ""]].[]gives[].
