Problem overview
The method groupAnagrams receives an array of strings and returns them grouped, so that each group holds words made of the same letters. The groups can come in any order.
In the example, ["eat", "tea", "tan", "ate", "nat", "bat"] splits into 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. An anagram uses every letter of the other word exactly once, so two words belong together when their letters, written in alphabetical order, are the same. Sorting eat, tea and ate all gives aet.
The statement sets a budget of O(n * log n * L * log L) time and O(n * L) extra space, where n is the number of strings and L their length. That is a hint at the plan: sort the array of strings, where every comparison sorts letters.
Approach: sort the words by their sorted letters
Call the sorted letters of a word its key. Anagrams have equal keys. If the array of words is sorted by key, all words with the same key end up next to each other, because equal keys compare as equal. Then one pass over the array can cut it into groups: start a new group whenever the key changes.
The cost matches the statement. Sorting the array takes O(n log n) comparisons. Each comparison computes two keys, and building a key sorts L letters, O(L log L). Comparing two keys takes O(L), which is smaller. Together that is O(n log n * L log L).
Step by step
The lesson first assumes a helper sorted(s) that returns the letters of s in alphabetical order, and writes it last.
- Sort
stringswith a comparator that comparesthis.sorted(a)andthis.sorted(b)usinglocaleCompare. It returns a negative number, zero or a positive number, which is what a comparator must return. Anagrams now sit side by side. - Create
resultas an emptystring[][], declared withconst, because the code only pushes into it. - Create
currentGroupas an emptystring[], declared withlet, because it will be reassigned. - Loop over the indices of
strings. - Push
strings[i]intocurrentGroup. In sorted order, it always belongs to the group being built. - Detect the end of a group. A group ends at the last index, or when the key of
strings[i]differs from the key ofstrings[i + 1]. The last-index test comes first:||skips its right side when the left side is true, sostrings[i + 1]is never needed past the end. - Store the group and start a new one: push
currentGroupintoresult, then assign a fresh empty array tocurrentGroup. - Return
result. - Write the helper
sorted. Place it beforegroupAnagramsin the class. - Build the key:
s.split('')turns the string into an array of characters,sort()orders them, andjoin('')glues them back into a string.
The solution in TypeScript
class Solution {
sorted(s: string): string {
return s.split('').sort().join('');
}
groupAnagrams(strings: string[]): string[][] {
strings.sort((a, b) => this.sorted(a).localeCompare(this.sorted(b)));
const result: string[][] = [];
let currentGroup: string[] = [];
for (let i = 0; i < strings.length; i++) {
currentGroup.push(strings[i]);
if (i == strings.length - 1 || this.sorted(strings[i]) != this.sorted(strings[i + 1])) {
result.push(currentGroup);
currentGroup = [];
}
}
return result;
}
}
On the example, this returns [["bat"],["eat","tea","ate"],["tan","nat"]]. The groups come out in the alphabetical order of their keys abt, aet and ant. The statement accepts any order.
Details worth knowing:
- Arrow functions and
this. An arrow function keeps thethisof the method around it, sothis.sortedworks inside the comparator. Afunctionexpression there would get its ownthisand fail. - Strings have no
sortmethod, but arrays do. That is why the helper goes throughsplitandjoin. - The default
sort()on characters. With no comparator, characters are ordered by their character codes, which is alphabetical for lowercase letters. Uppercase letters come before lowercase ones, and case matters for grouping:"Ab"and"ab"get the different keysAbandab, so they are not grouped together. - Reassign, don't clear.
currentGroup = []creates a new array. WritingcurrentGroup.length = 0instead would also empty the group already stored inresult, because both names point to the same array. - The input changes.
sortreorders the caller's array of strings.
Complexity
Time: O(n * log n * L * log L). The sort makes O(n log n) comparisons, and each one builds two keys at O(L log L) apiece. The grouping pass computes two keys per index, which is O(n * L log L), and doesn't add to the bound.
Space: O(n * L). The groups hold the original strings, and the keys built during comparisons are temporary, O(L) at a time. The keys are recomputed on every comparison instead of being stored, which saves memory and costs time.
Edge cases and common mistakes
- An empty array. The loop doesn't run, so the result is
[]. - The empty string.
[""]gives[[""]], a single group. - Equal words.
["a", "a"]gives[["a", "a"]]. - Words with different letters but the same length.
["ab", "ba", "cc"]gives[["ab", "ba"], ["cc"]]: the comparison is on sorted letters, not on length. - Reading
strings[i + 1]on the last index. Reading past the end givesundefinedin TypeScript, and callingsortedon it would then fail at run time. The last-index check prevents that. - Forgetting to push the last group. The condition has to treat the final index as the end of a group, because no next string exists to differ from it.
Testing
["eat", "tea", "tan", "ate", "nat", "bat"]gives[["bat"], ["eat", "tea", "ate"], ["tan", "nat"]].[]gives[].[""]gives[[""]].["ab", "ba", "cc"]gives[["ab", "ba"], ["cc"]].