Problem overview
The method groupAnagrams receives a string[] strings and returns a List<List<string>>. Each inner list holds words that are anagrams of each other, meaning they use exactly the same letters the same number of times. The groups can be returned in any order.
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; and bat stands alone. One valid answer is [["eat", "tea", "ate"], ["tan", "nat"], ["bat"]].
The statement allows O(n * L * log L) time and O(n * L) extra space, where n is the number of words and L is the length of a word. Note that the method name starts with a lowercase g in this lesson. The editor above uses that exact spelling, so keep it.
Approach: sorted letters as a group key
Two words are anagrams exactly when their letters, sorted, give the same string. "eat", "tea" and "ate" all become "aet"; "tan" and "nat" become "ant"; "bat" becomes "abt". That sorted form is a canonical key for the whole group.
Comparing every pair of words would take O(n² * L) or worse. Instead, compute the key for each word and use a dictionary from key to list of words. Each word is routed to its group with one dictionary lookup, so the work per word is the sort, O(L log L), plus hashing the key, O(L). Over n words that is O(n * L * log L). The dictionary stores every word once, plus the keys, which is O(n * L) space.
Step by step
- Create
groupBySorted, aDictionary<string, List<string>>. Keys are sorted forms and values are the words found with that form. - Loop over
stringswithforeach, usingsfor the current word. - Build the sorted key. Copy the word into a
char[]withToCharArray(), sort it withArray.Sort, and make a string from it withnew string(temp). Strings are immutable in C#, so you cannot sort one in place: you sort a copy of its characters and build a new string. - Make sure the group exists. If
groupBySorteddoes not containsortedString, assign a new emptyList<string>to that key. - Add the word to
groupBySorted[sortedString]. The indexer returns the list stored inside the dictionary, soAddchanges that list directly. - Return the groups.
groupBySorted.Valuesis the collection of all lists. Passing it to theList<List<string>>constructor copies them into the list the method must return.
The solution in C#
class Solution {
public List<List<string>> groupAnagrams(string[] strings) {
Dictionary<string, List<string>> groupBySorted = new Dictionary<string, List<string>>();
foreach (string s in strings) {
char[] temp = s.ToCharArray();
Array.Sort(temp);
string sortedString = new string(temp);
if (!groupBySorted.ContainsKey(sortedString)) {
groupBySorted[sortedString] = new List<string>();
}
groupBySorted[sortedString].Add(s);
}
return new List<List<string>>(groupBySorted.Values);
}
}
On the example, the words arrive in this order and the dictionary grows like this: eat creates the key aet; tea joins it; tan creates ant; ate joins aet; nat joins ant; and bat creates abt. Running this exact code on that input gives the groups [eat, tea, ate], [tan, nat] and [bat], in that order.
C# details:
- Reading versus writing a key. Reading
groupBySorted[key]for a missing key throwsKeyNotFoundException. Assigning to it adds the key. That is why theifwithContainsKeycomes before the read on the next line. - Lists are reference types. The dictionary holds a reference to each list, so adding through
groupBySorted[sortedString]grows the list that the dictionary stores. No copy is involved. - Order of the groups. A dictionary does not promise any enumeration order. In practice, one that only gets additions lists its entries in insertion order, as above, but that is not guaranteed. The lesson accepts any order.
- The final copy.
new List<List<string>>(groupBySorted.Values)copies the references to the inner lists, not the inner lists themselves. It is needed becauseValueshas a different type from the declared return type. - Usings.
DictionaryandListneedSystem.Collections.Generic, andArray.Sortis inSystem.
Complexity
Time: O(n * L * log L). For each of the n words, copying the characters is O(L), sorting is O(L log L), and hashing the key and comparing it with a stored key is O(L). The sort dominates.
Space: O(n * L). The dictionary keys and the lists together hold about two copies of each word's characters.
Edge cases and common mistakes
- Empty array. The loop does nothing and the result is an empty list.
- Empty string.
""has the sorted key"", which is a valid dictionary key, so all empty strings form one group. - A word with no anagram. It still appears, alone in a list of one, as
batdoes above. - Repeated words. Two copies of
"abc"are anagrams of each other and both are kept in the same group. - Case.
"Eat"and"tea"produce different keys, because uppercase letters sort before lowercase ones and are different characters. If the problem demanded case-insensitive grouping, you would lowercase the word first. - Sorting the string directly. Strings have no sort method, and they cannot be changed in place. Go through a
char[]. - Forgetting to add the word. Creating the empty list without adding
sproduces groups with missing words.
Testing
["eat", "tea", "tan", "ate", "nat", "bat"]gives the three groups above.["a"]gives[["a"]].[]gives an empty list.