Problem overview
The method groupAnagrams receives a string[] called strings and returns a List<List<string>>. Each inner list collects words that are anagrams of each other, meaning one can be rearranged into the other using every letter exactly once. The groups can come back 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. Running the reference solution on this input returns [bat], [eat, tea, ate] and [tan, nat]. The groups and their order differ from the statement's listing, which is fine, because any order is accepted.
Approach: sort the words by their sorted letters
Two words are anagrams exactly when their letters, sorted alphabetically, give the same string. eat, tea and ate all become aet. That string works as a signature for the group.
The lesson's idea is to sort the whole array of words by this signature. Words with equal signatures end up next to each other, so one pass can cut the array into groups: whenever the next word's signature differs from the current one, the current group is complete.
The statement allows O(n * log n * L * log L) time, where n is the number of words and L the longest word. Sorting the array makes O(n log n) comparisons, and each comparison sorts two words' letters at O(L log L) each. Extra space is O(n * L) for the result and the temporary character arrays.
Step by step
- Assume a helper
Sorted(s)that returns the letters ofsin alphabetical order. It is written last. - Sort
stringswith a comparison.Array.Sortaccepts a lambda(a, b) => ...that returns a negative number, zero or a positive number. The lambda replacesaandbwith their sorted forms and compares those withCompareTo. Reassigning the parameters changes only the values being compared; the array keeps the original words. - Create
result, an emptyList<List<string>>for the finished groups. - Create
currentGroup, an emptyList<string>for the group being built. - Loop over every index
ifrom 0 whilei < strings.Length. - Add the current word to
currentGroup. In sorted order, it always belongs to the group under construction. - Detect the end of a group. A group ends when
iis the last index or when the next word's signature differs from this word's. The last-index test goes first, and||skips the right side when the left side is true, sostrings[i + 1]is never read past the end. - Store the group and start a new one. Add
currentGrouptoresult, then assign a fresh list withnew(). - Return
resultafter the loop. - Write the helper
Sortedat the top of the class. - Copy the word into a
char[]withs.ToCharArray(). C# strings are immutable, so their characters can't be sorted in place. - Sort the character array with
Array.Sort. - Build a string from it with
new string(temp)and return it.
The solution in C#
class Solution {
public string Sorted(string s) {
char[] temp = s.ToCharArray();
Array.Sort(temp);
return new string(temp);
}
public List<List<string>> groupAnagrams(string[] strings) {
Array.Sort(strings, (a, b) => {
a = Sorted(a);
b = Sorted(b);
return a.ToLower().CompareTo(b.ToLower());
});
List<List<string>> result = new List<List<string>>();
List<string> currentGroup = new List<string>();
for (int i = 0; i < strings.Length; i++) {
currentGroup.Add(strings[i]);
if (i == strings.Length - 1 || Sorted(strings[i]).CompareTo(Sorted(strings[i + 1])) != 0) {
result.Add(currentGroup);
currentGroup = new();
}
}
return result;
}
}
The C# details to notice:
- The method name. This lesson names the method
groupAnagramswith a lowercase first letter, while C# convention would beGroupAnagrams. C# is case-sensitive, so use the name exactly as the editor has it. - Immutable strings. There is no way to sort a string's characters where they are.
ToCharArray()makes a mutable copy, andnew string(char[])turns it back. Callingtemp.ToString()on achar[]would return the type name, not the letters. - A lambda as a comparison.
Array.Sort(array, comparison)takes aComparison<T>, a delegate that receives two elements and returns anint. Lambda parameters are ordinary local variables, which is why assigning toaandbis allowed and doesn't touch the array. CompareToreturns an ordering, not a bool. It gives a negative number, 0 or a positive number, and 0 means the strings are equal. That is why the group boundary tests!= 0. Note thatstring.CompareTocompares using the current culture. For lowercase ASCII letters that gives the usual alphabetical order.- Why not
Clear().result.Add(currentGroup)stores a reference to the same list object, not a copy. CallingcurrentGroup.Clear()would empty the group already stored. Assigning a new list leaves the stored one alone. new()is a target-typed expression. The compiler takes the type from the variable, hereList<string>.- Order inside a group.
Array.Sortis not stable, so words with the same signature may appear in any order within their group.
Complexity
Time: O(n log n * L log L). The sort makes O(n log n) comparisons, and every comparison builds and sorts two signatures at O(L log L) each. The grouping pass computes two signatures per index, which is O(n * L log L), below the sort's cost.
Space: O(n * L). The result holds every word once, and the temporary signatures at any moment take O(L).
Edge cases and common mistakes
- No anagrams at all.
["a", "b"]gives two groups of one word each. - A single word. The loop runs once, the last-index test is true, and the result is one group with that word.
- An empty array. The loop never runs and the result is an empty list.
- Empty strings. Their signature is the empty string, so all empty strings land in one group.
- Reading past the end. Putting
strings[i + 1]before thei == strings.Length - 1test would throwIndexOutOfRangeExceptionon the last word. - Reusing one list. Adding the same
currentGroupobject toresultrepeatedly and clearing it leaves empty lists in the answer. - Forgetting the last group. A group is only stored when a boundary is detected, and the final group has no word after it. That is the job of the last-index test.
Testing
["eat", "tea", "tan", "ate", "nat", "bat"]gives three groups, as described above.["a"]gives[[a]].[]gives an empty list.["", "b", ""]gives two groups: the two empty strings together, andbalone.