Problem overview
The method groupAnagrams receives an array of strings and returns an array of groups, where each group holds the words that are anagrams of one another. Two words are anagrams when they use exactly the same letters the same number of times. The groups may come back in any order.
For ["eat", "tea", "tan", "ate", "nat", "bat"] there are three groups: eat, tea and ate together; tan and nat together; and bat alone. The solution below returns them as [["eat", "tea", "ate"], ["tan", "nat"], ["bat"]], which is the same grouping in a different order than the statement shows.
Approach: give every anagram the same key
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 the longest one. Comparing every pair of words would multiply the work by another n. A better idea is a canonical form: a value that is the same for all anagrams of a word and different for words that are not anagrams.
Sorting the letters gives exactly that. "eat", "tea" and "ate" all become "aet", while "tan" becomes "ant" and "bat" becomes "abt". Use the sorted string as the key of a dictionary whose values are lists of the original words. Each word is appended to the list under its key, and when the pass is over, the lists are the groups.
Sorting one word of length L costs O(L log L), and it happens once per word, so the total is O(n * L * log L). The dictionary stores every word and every key, which is O(n * L).
Step by step
- Create the dictionary.
groupBySortedis aconstempty object typed{ [key: string]: string[] }. That index signature reads "any string key, with an array of strings as the value". - Loop over the words. A
for...ofloop gives each word ass. - Build the key.
s.split("")turns the word into an array of characters,sort()orders them andjoin("")glues them back into a string. Strings have nosortmethod, which is why the detour through an array is needed. - Create the group if it is new. If the key is not yet in the object, store an empty array under it. The condition is
!(sortedString in groupBySorted); the parentheses matter because!binds tighter thanin. - Add the word. Push
sonto the array for its key. - Return the groups.
Object.values(groupBySorted)gives an array of the object's values, which are exactly the lists.
The solution in TypeScript
class Solution {
groupAnagrams(strings: string[]): string[][] {
const groupBySorted: { [key: string]: string[] } = {};
for (const s of strings) {
const sortedString = s.split("").sort().join("");
if (!(sortedString in groupBySorted)) {
groupBySorted[sortedString] = [];
}
groupBySorted[sortedString].push(s);
}
return Object.values(groupBySorted);
}
}- Sorting without a comparator is fine here. The default
sort()orders by string value, which is wrong for numbers ([10, 9, 1].sort()gives[1, 10, 9]) but exactly what we want for characters. All that matters is that equal letters always end up in the same order. - Uppercase and lowercase differ. Sorting puts
"A"before"a", and they are different characters, so"a"and"A"go into separate groups. - The object is a dictionary. It is declared
constbecause the variable is never reassigned. The contents still change when keys are added. - The order of
Object.values. Keys that look like whole numbers come first, in ascending numeric order, and the other keys follow in insertion order. For["21", "12", "3"]the result is[["3"], ["21", "12"]], because the keys are"12"and"3". The lesson accepts any order. inalso sees inherited names."toString" in {}istrue, because plain objects inherit properties. AMap<string, string[]>, withget,setand[...groups.values()], avoids the question and keeps insertion order.- Types are erased. The index signature is checked by the compiler only. At run time the object is an ordinary one.
The same idea with a Map
function groupMap(strings: string[]): string[][] {
const groups = new Map<string, string[]>();
for (const s of strings) {
const key = s.split("").sort().join("");
const group = groups.get(key);
if (group === undefined) {
groups.set(key, [s]);
} else {
group.push(s);
}
}
return [...groups.values()];
}It returns the same three groups for the example, in the order the keys first appeared. The logic is identical: one key per anagram class, one list per key. Use whichever form the problem or your team prefers.
Complexity
Time: O(n * L * log L). For each of the n words, splitting and joining take O(L) and sorting takes O(L log L). Dictionary lookups and pushes are O(1) on average, apart from hashing a key of length L, which is within O(L).
Space: O(n * L). The dictionary holds every word once as a list element and one sorted key per group.
Edge cases and common mistakes
- Empty array. The result is
[]. - Empty string. Its key is
"", so[""]gives[[""]]. - No anagrams. Every word forms a group of its own.
- Duplicate words. They are anagrams of themselves, so both copies appear in the same group.
- Forgetting to initialise the list. Without the
if, the firstpushwould run onundefinedand throw an error at run time. - Writing
!sortedString in groupBySorted. That negates the string first, so the test is nonsense and the compiler reports it. - Using the original word as the key. Then no two words ever share a key, and every group has one word.
Testing
["eat", "tea", "tan", "ate", "nat", "bat"]gives[["eat", "tea", "ate"], ["tan", "nat"], ["bat"]].[]gives[].[""]gives[[""]].["a", "A"]gives[["a"], ["A"]].