Problem overview
The function groupAnagrams receives a slice of strings, strs, and returns them grouped so that each group holds words that are anagrams of one another, which means they use the same letters the same number of times. The groups can come back in any order.
For ["eat", "tea", "tan", "ate", "nat", "bat"] the groups are eat, tea, ate, then tan, nat, then bat. The lesson's budget is 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: sort the words by their sorted letters
Two words are anagrams exactly when their letters, put in alphabetical order, give the same string. For "eat", "tea" and "ate" that string is "aet". This sorted form acts as a signature of the group.
So sort the whole slice with the signature as the sort key. Anagrams share a signature, so they end up next to each other. A single pass over the sorted slice then cuts it into groups: a group ends where the next word's signature differs.
The cost matches the lesson's note. Computing a signature sorts up to L letters, which is O(L log L). The sort of the slice makes O(n log n) comparisons, and each comparison computes two signatures. The final pass computes two more per word, which is cheaper. Faster ways exist, such as counting letters or using a map keyed by the signature, but this version uses only sorting.
Step by step
- Assume a helper
sorted(s)onSolutionthat returns a string's letters in alphabetical order. It is written at the end. - Sort
strswithsort.Slice, whose less function comparessol.sorted(strs[i])withsol.sorted(strs[j]). The parameter is calledstrsbecausestringsis the name of a standard package. - Declare
result, an empty[][]string, to collect the finished groups. - Declare
currentGroup, an empty[]string, for the group being built. - Loop over every index
iofstrs, so that each word can be compared with the next. - Append
strs[i]tocurrentGroup. In sorted order every word belongs to the group in progress. - Detect the end of a group: either
iis the last index, or the signature ofstrs[i]differs from that ofstrs[i+1]. The last-index test comes first, so with||the right side is skipped andstrs[i+1]is never read past the end. - Append
currentGrouptoresultwhen the group is complete. - Start a new group by assigning a new empty
[]string{}tocurrentGroup. - Return
result. - Write the helper
sortedwith the same receiver,sol Solution, taking a string and returning a string. - Copy the string into a byte slice
bwith[]byte(s). - Sort
bwithsort.Slice, comparingb[i] < b[j]. - Return
string(b).
The solution in Go
func (sol Solution) sorted(s string) string {
b := []byte(s)
sort.Slice(b, func(i, j int) bool { return b[i] < b[j] })
return string(b)
}
func (sol Solution) groupAnagrams(strs []string) [][]string {
sort.Slice(strs, func(i, j int) bool {
return sol.sorted(strs[i]) < sol.sorted(strs[j])
})
result := [][]string{}
currentGroup := []string{}
for i := 0; i < len(strs); i++ {
currentGroup = append(currentGroup, strs[i])
if i == len(strs)-1 || sol.sorted(strs[i]) != sol.sorted(strs[i+1]) {
result = append(result, currentGroup)
currentGroup = []string{}
}
}
return result
}
Go details worth a closer look:
- Strings are immutable. A Go string cannot be changed in place, so the helper copies it into a
[]byte, sorts that, and converts it back. The words here are lowercase English letters, one byte each, so sorting bytes sorts letters. Words with multi-byte characters would need[]runeinstead. sort.Slicetakes any slice and a less function,less(i, j), which says whether the element at indexigoes before the one atj. It sorts the slice in place. The packagesortmust be imported.- The input slice is reordered. Because
sort.Sliceworks in place, the caller'sstrscomes back sorted by signature. For the example input it becomes[bat eat tea ate tan nat]. - The order is not stable.
sort.Slicedoes not keep equal elements in their original order, so the words inside a group can come out in any order. The example can return[[bat] [eat tea ate] [tan nat]]. The groups themselves follow the alphabetical order of their signatures:abt,aet,ant. - A fresh slice per group. Writing
currentGroup = []string{}gives the next group its own storage. Resetting withcurrentGroup = currentGroup[:0]would reuse the backing array, and later appends would overwrite what was already stored inresult. In a small experiment that stores each group after resetting that way, two single-word groupscatanddogboth print as[dog]. - Value receiver.
Solutionhas no fields, so the receiversol Solutionis only the way to call the helper as a method.
Complexity
Time: O(n * log n * L * log L). The sort does O(n log n) comparisons. Each comparison builds two signatures, each costing O(L log L). The grouping pass computes O(n) more signatures, which does not change the bound.
Space: O(n * L). The result holds all n strings, which are up to L characters each. The helper allocates a copy of one string at a time, so the working memory beyond the result is O(L).
Edge cases and common mistakes
- An empty slice. The loop never runs and the function returns an empty, non-nil
[][]string{}. - The empty string.
[""]gives one group that holds the empty string: its signature is the empty string. - A single word.
["a"]gives[["a"]], since the last-index test closes the group. - Different lengths.
["ab", "abc", "ba"]gives the groupsab, baandabc. Words of different lengths never share a signature. - Reading past the end. Checking
strs[i+1]before checkingi == len(strs)-1would panic with an index out of range error on the last word. - Forgetting the last group. Closing a group only when the signature changes would drop the final group; the last-index test is what stores it.
- Expecting a fixed order. Neither the order of the groups nor of the words inside them is promised, so compare results after sorting if you test by hand.
Testing
["eat", "tea", "tan", "ate", "nat", "bat"]gives three groups:bat;tan, nat; andeat, tea, ate, in some order.[""]gives[[""]].["a"]gives[["a"]].["ab", "abc", "ba"]gives the groupsab, baandabc.
