Problem overview
The method groupAnagrams receives an array of strings and returns them grouped so that every group holds words made from exactly the same letters. The groups can come back in any order.
For ["eat", "tea", "tan", "ate", "nat", "bat"] there are 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. Any arrangement of those groups is correct, for example [["bat"], ["eat", "tea", "ate"], ["tan", "nat"]].
Approach: sort the words by their sorted letters
Two words are anagrams exactly when their letters, put in alphabetical order, give the same string. "eat", "tea" and "ate" all become "aet". That string works as a signature for the whole group.
If you sort the array of words by that signature, all the anagrams of a word end up next to each other. Then a single pass can cut the array into groups: whenever the next word has a different signature, the current group is complete.
The statement's budget, O(n * log n * L * log L), comes from this plan. Each comparison builds two signatures, and sorting a word of length L costs L log L. Doing that for each of the n log n comparisons gives the bound.
Here is the sorted order for the example. The signatures are eat to aet, tea to aet, tan to ant, ate to aet, nat to ant and bat to abt. Sorted by signature, the signatures run abt, then aet three times, then ant twice. The pass over the array cuts at each change, which gives the groups bat; eat, tea, ate; and tan, nat, though the words inside a group can appear in a different order.
Step by step
- Copy the input. Parameters are constants, so
var strs = stringsmakes a mutable copy. - Sort the copy with a closure that compares signatures:
sorted($0) < sorted($1). Words with equal signatures are now adjacent. - Prepare two variables:
result, an empty[[String]]for the finished groups, andcurrentGroup, an empty[String]for the group being built. - Loop over every index
iin0..<strs.count. - Add the current word to
currentGroup. In sorted order it always belongs to the group in progress. - Detect the end of a group. A group ends at the last index, or when the next word's signature differs. Test the last index first with
||, sostrs[i + 1]is never read past the end. - Close the group: append
currentGrouptoresult, then reset it to an empty array. - Return
resultafter the loop. - Write the helper
sorted(_:): turn the string into an array of characters, sort that array, and turn it back into a string.
The solution in Swift
class Solution {
func sorted(_ s: String) -> String {
var chars = Array(s)
chars.sort()
return String(chars)
}
func groupAnagrams(_ strings: [String]) -> [[String]] {
var strs = strings
strs.sort { sorted($0) < sorted($1) }
var result: [[String]] = []
var currentGroup: [String] = []
for i in 0..<strs.count {
currentGroup.append(strs[i])
if i == strs.count - 1 || sorted(strs[i]) != sorted(strs[i + 1]) {
result.append(currentGroup)
currentGroup = []
}
}
return result
}
}
The Swift details worth knowing:
- Strings can't be sorted in place. A
Stringdoesn't let you swap its characters by integer index.Array(s)produces an[Character], which can be sorted withsort(), andString(chars)joins the characters back together. - The helper's name. The method is called
sorted, like the built-in array method, but it takes aStringand is called assorted($0)from inside the class. It is a method ofSolution, not a call on the array. - Short-circuit
||. Wheni == strs.count - 1is true, the right side isn't evaluated. At the last index,strs[i + 1]doesn't exist, and reading it would crash. - Arrays are values.
result.append(currentGroup)stores a copy. SettingcurrentGroup = []afterwards doesn't touch the stored group. - Characters compare by value. Sorting characters orders them by their Unicode value, so uppercase letters come before lowercase.
"Tea"becomes"Tae"while"eat"becomes"aet", so the two are not grouped.
Complexity
Let n be the number of words and L the average word length.
Time: O(n log n * L log L). The sort makes O(n log n) comparisons. Each builds two signatures at O(L log L) each and compares them in O(L). The final pass makes n more signature comparisons, which is smaller.
Space: O(n * L). The copy of the array holds the words, and the result holds them again. Each signature is a temporary string of length L.
Edge cases and common mistakes
- Empty array. The loop range
0..<0is empty, and the result is[]. - Empty string.
[""]gives[[""]]. An empty word has an empty signature and forms its own group. - Repeated words.
["ab", "ba", "ab"]gives one group of three, because repeats share the signature. - Forgetting the last group. The group is only closed when the signature changes. The
i == strs.count - 1test closes the final group, which has no next word to differ from. - Reading
strs[i + 1]first. Reversing the two conditions crashes on the last word. - Not resetting
currentGroup. The next group would start with the previous words still in it.
Testing
["eat", "tea", "tan", "ate", "nat", "bat"]gives three groups of sizes 3, 2 and 1. The order of the groups and of the words inside them may vary between implementations.[]gives[].[""]gives[[""]].["ab", "ba", "ab"]gives one group of three words.
