Problem overview
The method groupAnagrams receives an array of strings and returns them grouped so that words which are anagrams of each other end up together. An anagram is a rearrangement of the same letters, using every letter exactly once. The groups can come back in any order.
For ["eat", "tea", "tan", "ate", "nat", "bat"] the groups are ["eat", "tea", "ate"], ["tan", "nat"] and ["bat"].
The statement asks for O(n * L * log L) time and O(n * L) extra space, where n is the number of strings and L is the length of the longest one.
Approach: a key that all anagrams share
Comparing every pair of words would take O(n²) comparisons, each with its own cost. Instead, give every word a key such that two words have the same key exactly when they are anagrams. Then a dictionary can collect the words under their keys in one pass.
Sorting the letters of a word makes such a key. "eat", "tea" and "ate" all become "aet", while "tan" and "nat" become "ant". Rearranging letters can't change the sorted result, and two words with the same sorted letters use the same letters the same number of times.
Sorting one word of length L costs O(L log L), and doing it for n words gives the O(n * L * log L) time bound. The dictionary stores every word once, plus its key, which is O(n * L) space.
Step by step
- Create the dictionary.
groupBySortedis avarof type[String: [String]], mapping each sorted key to the words that share it. - Loop over the words with
for s in strings, so each word can be routed to its group. - Build the key.
s.sorted()returns the characters ofsin order as an array, andString(...)joins them back into a string. Store it inlet sortedString. - Make sure the group exists. If
groupBySorted[sortedString]is stillnil, assign it an empty array. - Add the word. Append
sto the array stored under that key. The earlier step guarantees the key exists, so force-unwrapping with!is safe here. - Return the groups. The dictionary's
valuesare exactly the groups; wrapping them inArray(...)gives the[[String]]the method returns.
Tracing the example
Processing "eat" creates the key "aet" with the group ["eat"]. "tea" has the same key, so the group becomes ["eat", "tea"]. "tan" creates the key "ant". "ate" joins the "aet" group, "nat" joins "ant", and "bat" creates the key "abt". The dictionary ends with three entries, and its values are the three groups.
The solution in Swift
class Solution {
func groupAnagrams(_ strings: [String]) -> [[String]] {
var groupBySorted: [String: [String]] = [:]
for s in strings {
let sortedString = String(s.sorted())
if groupBySorted[sortedString] == nil {
groupBySorted[sortedString] = []
}
groupBySorted[sortedString]!.append(s)
}
return Array(groupBySorted.values)
}
}
Swift details worth a closer look:
- Sorting a string. A
Stringis a collection ofCharactervalues, so"tea".sorted()is the array["a", "e", "t"]. Passing that array toString(...)produces"aet". - Dictionary subscripts are optional.
groupBySorted[sortedString]has the type[String]?and isnilfor a missing key. That is why comparing withniltells you whether the group exists. - Appending through the dictionary.
groupBySorted[sortedString]!.append(s)changes the array stored in the dictionary itself. Arrays are value types, but the expression writes through the subscript, so the dictionary sees the new element. - A shorter form.
groupBySorted[sortedString, default: []].append(s)does the existence check and the append in one line. - Order of the result. Dictionary order is unspecified and can differ between runs, so the groups may come back in any order. Inside each group the words keep the order in which they appeared in the input, for example
["eat", "tea", "ate"]. valuesis a view.groupBySorted.valuesis not an array;Array(...)copies it into one.
The sorted word is not the only possible key. Counting how many times each letter appears also identifies an anagram class, and for a fixed alphabet it avoids the sort. This lesson uses the sorted word because it is short and works for any characters.
Complexity
Time: O(n * L * log L). Each of the n words is sorted in O(L log L). Hashing a key of length up to L costs O(L), which the sort already dominates. Dictionary operations are constant time on average apart from that hashing.
Space: O(n * L). The dictionary holds n words plus up to n keys of length up to L.
Edge cases and common mistakes
- Empty input array. Returns
[]. - Empty string.
[""]returns[[""]]. The key is the empty string, which is a valid dictionary key. - Identical words.
["a", "a"]returns one group,[["a", "a"]]. Both copies are kept. - Words that merely share letters.
"aab"and"ab"sort to different keys,"aab"and"ab", so they are not anagrams. Comparing sets of letters instead of sorted letters would wrongly merge them. - Case.
"Eat"and"tea"get different keys, because uppercase and lowercase letters are different characters. - Comparing results. Because the group order varies, sort the groups before comparing them with an expected answer.
Testing
["eat", "tea", "tan", "ate", "nat", "bat"]gives the three groups listed above, in any order.[]gives[].[""]gives[[""]].["a", "a"]gives[["a", "a"]].
