Problem overview
The method groupAnagrams(strings) receives an array of strings and returns an array of groups, where each group holds the strings that are anagrams of each other. Two strings are anagrams when they use exactly the same letters the same number of times, in any order. The groups can come back in any order.
For ["eat", "tea", "tan", "ate", "nat", "bat"], the answer has three groups: "eat", "tea" and "ate" together, "tan" and "nat" together, and "bat" alone. The solution below returns them as [["bat"], ["eat", "tea", "ate"], ["tan", "nat"]], which is the same grouping in a different order.
The lesson asks for O(n * log n * L * log L) time and O(n * L) extra space, where n is the number of strings and L the length of the longest one.
Approach: a sorted word is a signature
Comparing every string with every other string and checking each pair letter by letter works, but it is slow. A better idea is to give every string a signature that is the same for all of its anagrams. The simplest signature is the string's letters in alphabetical order: "eat", "tea" and "ate" all become "aet", while "tan" and "nat" become "ant". Two strings are anagrams exactly when their signatures are equal.
Once there is a signature, there are two common ways to use it. One is a Map from signature to group, which needs a single pass. This lesson uses the other: sort the whole array by signature. After that, all anagrams of a word sit next to each other, and one pass over the array can cut it into groups wherever the signature changes. The sort-based version needs no hash map, and it is the version the lesson's complexity budget describes.
The cost is easy to account for. Building one signature sorts at most L letters, which is O(L log L). Sorting the array makes O(n log n) comparisons, and each comparison builds two signatures, so the sort costs O(n log n * L log L). The grouping pass builds up to two signatures per string, which is smaller.
Step by step
- Assume the signature helper. The lesson starts by assuming a method
sorted(s)that returns the letters ofsin alphabetical order, and writes it at the end. - Sort
stringsby signature. The comparator receives two strings,aandb, and returnsthis.sorted(a).localeCompare(this.sorted(b)).localeComparegives a negative number, zero or a positive number, which is whatsortexpects. An arrow function keeps thethisofgroupAnagrams, sothis.sortedstill works inside it. - Create
resultas an empty array. It collects the finished groups. - Create
currentGroupas another empty array. It holds the group being built. - Loop over every index
ifrom0tostrings.length - 1. - Push
strings[i]intocurrentGroup. In sorted order the current string always belongs to the group in progress. - Detect the end of a group. A group ends at the last index, or when the signature of
strings[i]differs from the signature ofstrings[i + 1]. The last-index check comes first on purpose:||does not evaluate its right side when the left side is true, sostrings[i + 1]is never read past the end. - Close the group. Push
currentGroupintoresult, then assign a new empty array tocurrentGroup. - Return
resultafter the loop. - Finally, write
sorted(s)as a method of the class:s.split("").sort().join("").
The solution in JavaScript
var algorithms = require('algorithms')
class Solution {
sorted(s) {
return s.split("").sort().join("");
}
groupAnagrams(strings) {
strings.sort((a, b) => {
return this.sorted(a).localeCompare(this.sorted(b));
});
let result = [];
let currentGroup = [];
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
}
}
The details worth knowing:
- Why
currentGroup = []and notcurrentGroup.length = 0. An array in JavaScript is an object, andresult.push(currentGroup)stores a reference to it, not a copy. Emptying the same array afterwards would also empty the group already insideresult, leaving[[]]. Assigning a fresh array leaves the stored one alone. - Splitting and joining. Strings have no
sortmethod, but arrays do.split("")turns the string into an array of single characters,sort()orders them, andjoin("")glues them back together. Without a comparator,sort()compares elements as strings by their UTF-16 code units. For single lowercase letters that is alphabetical order. The signature only has to be the same for anagrams, and it is, because the same letters always sort into the same order. - The sort changes the input.
strings.sort(...)reorders the array that was passed in. After the call,stringsis in signature order. If the caller needs the original order, sort a copy with[...strings]first. - Why the groups are contiguous. The comparator orders strings by signature, so all strings with the same signature end up in one block. A group can never be split in two, which is what makes the single pass correct.
- The first line.
var algorithms = require('algorithms')loads a helper library that the lesson provides. The solution never uses it. ==and!=. Both sides are strings here, so these behave like===and!==. Using the strict versions is a good habit.
Complexity
Time: O(n * log n * L * log L). The sort makes O(n log n) comparisons, and each one sorts the letters of two strings at O(L log L) apiece. The grouping loop adds O(n * L log L), which does not change the total.
Space: O(n * L). The result holds all n strings, and a signature takes O(L) temporary space.
The signature is rebuilt every time it is needed. Computing each signature once and keeping it would save work, and a Map from signature to group removes the array sort altogether and brings the time down to O(n * L log L).
Edge cases and common mistakes
- Empty array. The loop never runs and the result is
[]. - Empty string.
[""]gives[[""]]. Two empty strings are anagrams of each other, so["", "b", ""]gives[["", ""], ["b"]]. - Duplicates. Equal strings have equal signatures and land in the same group:
["abc", "abc", "cab"]gives one group of three. - A single string.
["a"]gives[["a"]]. The last-index check closes the group. - Reusing one group array. Clearing
currentGroupwithlength = 0instead of creating a new array empties the groups already stored. - Reading past the end. If the signature comparison is written before the last-index check, the loop reads
strings[strings.length], which isundefined, and callingspliton it throws aTypeError. - Mixed case.
"Ab"and"ab"have different signatures, because uppercase letters sort before lowercase ones by code unit. Lowercase the strings first if they should count as anagrams.
Testing
["eat", "tea", "tan", "ate", "nat", "bat"]gives[["bat"], ["eat", "tea", "ate"], ["tan", "nat"]].[""]gives[[""]].["a"]gives[["a"]].[]gives[].["abc", "abc", "cab"]gives[["abc", "abc", "cab"]].
