Problem overview
The method groupAnagrams receives an Array[String] called strings and returns a List[List[String]]. Each inner list holds the words that are anagrams of each other: words made of exactly the same letters in a different order. The groups can come back in any order.
For Array("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. "bat" is alone.
The lesson's budget is O(n * L * log L) time and O(n * L) extra space, where n is the number of words and L the length of the longest one.
Approach: use the sorted letters as a key
Comparing every pair of words by hand would be slow. Instead, find a value that is the same for all anagrams and different for everything else. Sorting a word's letters does that: "eat", "tea" and "ate" all become "aet", while "tan" and "nat" become "ant", and "bat" becomes "abt". Two words are anagrams exactly when their sorted forms are equal.
So use the sorted form as a hash map key, and let the value be the list of original words with that key. One pass over the input puts each word into its group. Sorting one word of length L costs O(L log L), and doing it for n words gives the lesson's O(n * L * log L).
Step by step
- Create the map.
groupBySortedis ascala.collection.mutable.LinkedHashMap[String, scala.collection.mutable.ListBuffer[String]]. Keys are sorted words, values are growable buffers of words. ALinkedHashMapkeeps keys in insertion order, which makes the output order predictable. - Loop over the words with
for (s <- strings). - Build the key.
s.toCharArray.sortedturns the word into an array of characters and sorts it, producing a new array.new String(...)turns that array back into aString, which is what the map needs as a key. - Create a missing group. If the map doesn't contain the key yet, store an empty
ListBuffer[String]()under it withgroupBySorted(sortedString) = .... - Append the word.
groupBySorted(sortedString) += sreads the buffer from the map and appends to it in place. - Build the result.
groupBySorted.valuesare the buffers..map(_.toList)converts each buffer to an immutableList, and the final.toListmakes the outer collection aListtoo. This is the last expression, so it is the method's value.
The solution in Scala
class Solution {
def groupAnagrams(strings: Array[String]): List[List[String]] = {
val groupBySorted = scala.collection.mutable.LinkedHashMap[String, scala.collection.mutable.ListBuffer[String]]()
for (s <- strings) {
val sortedString = new String(s.toCharArray.sorted)
if (!groupBySorted.contains(sortedString)) {
groupBySorted(sortedString) = scala.collection.mutable.ListBuffer[String]()
}
groupBySorted(sortedString) += s
}
groupBySorted.values.map(_.toList).toList
}
}
On the example, this returns List(List(eat, tea, ate), List(tan, nat), List(bat)). The groups follow the order in which their first word appeared, and each group keeps the input order of its words.
The Scala details worth a closer look:
- Two kinds of collections. The buffers and the map are mutable so they can grow while the loop runs. The result is converted to immutable
Lists because that is the declared return type. - Mutating through the map.
groupBySorted(sortedString)returns the buffer object itself, not a copy. Appending with+=therefore changes the buffer that the map holds. sortedcopies. On an array,sortedreturns a new sorted array and leaves the original alone. For anArray[Char]the characters are ordered by their numeric code, so an uppercase letter sorts before every lowercase one.- Why the
new String. An array has no content-based equality, so two arrays holding the same letters are different keys. AStringcompares by content, so equal strings land on the same key..mkStringwould also work, giving the same string. - Placeholder shorthand.
_.toListmeans "a function that takes one argument and callstoListon it", the same asbuffer => buffer.toList. - Value of the method. The last line is an expression with no
return, which Scala uses as the method's result.
Complexity
Time: O(n * L * log L). For each of the n words, creating the character array is O(L), sorting it is O(L log L), and hashing the key string is O(L). The sort dominates. Appending to a buffer and the final conversions add O(n * L).
Space: O(n * L). The map stores one key per group and every word once, and the final lists hold the words again, which is still proportional to the total number of characters.
Edge cases and common mistakes
- Empty input. An empty array gives an empty list.
- Empty string.
Array("")gives one group that holds the empty string. The sorted form of an empty string is an empty string, so that is the key. Printed, the result looks likeList(List()), because the empty string shows as nothing. - Repeated words.
Array("a", "a")gives one group with both copies. They are anagrams of each other. - Using the original word as the key. Then every word gets its own group and nothing is grouped.
- Using an array as the key. Equal letters in different arrays are different keys, so no grouping happens. Convert the sorted letters to a string.
- Forgetting to create the group. Appending to
groupBySorted(sortedString)before the key exists throws aNoSuchElementException. - Case.
"Tea"and"eat"are not grouped, since'T'and't'are different characters. Lower-case the words first if you need that.
Testing
Array("eat", "tea", "tan", "ate", "nat", "bat")gives three groups: the two-word grouptan, nat, the three-word groupeat, tea, ateand the singlebat.Array("a", "a")gives one group with two entries.Array("ab", "ba", "ab")gives one group of three.Array()gives an empty list.
