Problem overview
The function group_anagrams receives a vector of strings, strings, and returns a vector of groups. Strings that are anagrams of each other, meaning one is a rearrangement of the other's letters, go into the same group. The order of the groups, and of the strings inside a group, is free.
For ["eat", "tea", "tan", "ate", "nat", "bat"] there are three groups: eat, tea and ate share the letters a, e and t; tan and nat share a, n and t; bat stands alone.
The lesson accepts O(n * log n * L * log L) time and O(n * L) extra space, with n strings of length up to L.
Approach: sort by the sorted letters
Two strings are anagrams exactly when their letters in alphabetical order are the same string. So "eat", "tea" and "ate" all become "aet", and "tan" and "nat" both become "ant". That sorted form works as a label for the group.
Sorting the vector of strings by that label puts every anagram group in one block of neighbours. The solution then walks through the sorted vector and cuts it into groups wherever the label changes. This costs one sort of the strings plus one pass.
The cost has two parts. Sorting n strings needs about n log n comparisons. Each comparison here builds the sorted-letters label of both strings, which costs O(L log L) for sorting the letters of a string of length L. Multiplied, that is the O(n * log n * L * log L) of the statement. The labels are built as temporary strings, so memory stays around O(n * L) for the groups.
After sorting, the example looks like this:
["bat", "eat", "tea", "ate", "tan", "nat"]
The labels are abt, aet, aet, aet, ant and ant, in that order. The label changes after bat, after ate and after nat, so there are three groups.
Step by step
- Sort the strings by their label. The parameter is
mut strings, so the function can sort it. Callsort_bywith a closure that comparesSelf::sorted_str(a)withSelf::sorted_str(b)usingcmp. The helper takes noself, so it is called throughSelf::. - Create the containers.
resultis an empty, mutableVec<Vec<String>>for the finished groups, andcurrent_groupis an empty, mutableVec<String>for the group being built. - Store the length in
n, for the loop and the last-index test. - Loop over
iin0..n. - Add the current string to
current_group. In sorted order it always belongs to the group being built. Push a clone, because indexing a vector can't move aStringout of it. - Detect the end of a group. A group ends when
i == n - 1or when the label ofstrings[i]differs from the label ofstrings[i + 1]. The last-index check goes first, so the right side is never evaluated past the end. - Close the group. Push
current_groupontoresultand givecurrent_groupa new emptyVec. - Return
resultas the last expression. - Write the helper. In
sorted_str, collect the characters ofsinto a mutableVec<char>namedchars, sort it, then collect it back into aString.
The solution in Rust
impl Solution {
fn sorted_str(s: &str) -> String {
let mut chars: Vec<char> = s.chars().collect();
chars.sort();
chars.iter().collect()
}
fn group_anagrams(mut strings: Vec<String>) -> Vec<Vec<String>> {
strings.sort_by(|a, b| Self::sorted_str(a).cmp(&Self::sorted_str(b)));
let mut result: Vec<Vec<String>> = Vec::new();
let mut current_group: Vec<String> = Vec::new();
let n = strings.len();
for i in 0..n {
current_group.push(strings[i].clone());
if i == n - 1 || Self::sorted_str(&strings[i]) != Self::sorted_str(&strings[i + 1]) {
result.push(current_group);
current_group = Vec::new();
}
}
result
}
}
The Rust details worth a closer look:
- Letters as
charvalues. AStringcan't be sorted directly, and indexing it by position is not allowed, because it is UTF-8 bytes.s.chars().collect()gives aVec<char>that can be sorted. Characters sort by their Unicode value, so for lowercase letters this is alphabetical order. - Collecting twice.
collect()builds whatever the surrounding type asks for. The annotation oncharsmakes it aVec<char>, and the function's return type makes the last one aString.chars.iter()yields&char, andStringcan be built from those. - Reference coercion.
sorted_strtakes a&str. Passing a&String, as&strings[i]or the closure'saandbdo, works because Rust converts it automatically. - Comparing with
cmp.cmptakes its argument by reference, hence&Self::sorted_str(b), and returns theOrderingthatsort_byneeds. Strings compare in dictionary order. - Moving the group.
result.push(current_group)moves the vector intoresult, socurrent_groupcan't be used until it is assigned a new value. That is why the next line assignsVec::new(). - Cloning.
strings[i].clone()copies the string, sincestringsis still needed for the label comparison on the next line. - The subtraction
n - 1. It is evaluated only inside the loop. For an empty vector the loop never runs, so there is no underflow of the unsignedn.
Complexity
Time: O(n * log n * L * log L). The sort makes O(n log n) comparisons, and each builds two labels at O(L log L). The final pass builds two labels per element, which is O(n * L log L) and smaller than the sort.
Space: O(n * L). The groups hold a copy of every string. The labels are temporary and each lasts for a single comparison.
Edge cases and common mistakes
- Empty vector. The loop doesn't run, and the result is an empty vector of groups.
- The empty string. Its label is the empty string, so
[""]gives[[""]]. - Identical strings. They are anagrams of each other.
["a", "a", "b"]gives[["a", "a"], ["b"]]. - Same length is not enough.
"tan"and"tab"have the same length but different letters, so they have different labels. - Forgetting to start a new group. Without assigning a fresh
Vec::new(), the previous group would keep growing, and the compiler would also complain about using a moved value. - Checking the next string at the last index. Reading
strings[i + 1]wheniis the last index panics. Putting thei == n - 1test first with||avoids it. - Order of the output. The groups come out ordered by label, and strings in a group keep their input order. For the example the result is
[["bat"], ["eat", "tea", "ate"], ["tan", "nat"]], which is a valid answer because any order is accepted.
Testing
["eat", "tea", "tan", "ate", "nat", "bat"]gives[["bat"], ["eat", "tea", "ate"], ["tan", "nat"]].[]gives[].[""]gives[[""]].["a", "a", "b"]gives[["a", "a"], ["b"]].
