Problem overview
The method groupAnagrams receives a list of strings and returns a list of groups. Each group holds the strings that are anagrams of each other, which means they use exactly the same letters the same number of times. The groups and the words inside them can come 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. One valid answer is [['bat'], ['eat', 'tea', 'ate'], ['tan', 'nat']].
The statement allows O(n * log n * L * log L) time and O(n * L) extra space, where n is the number of strings and L is the length of a word. It also says faster solutions exist, and this lesson does not use them.
Approach: sort the words so anagrams sit together
Two words are anagrams exactly when their letters, sorted, give the same sequence. sorted("eat"), sorted("tea") and sorted("ate") all give ['a', 'e', 't']. That sorted sequence works as a signature: words with the same signature belong in the same group.
The idea of this lesson is to sort the whole list of words by that signature. After sorting, every group of anagrams is a run of neighbours, because words with equal keys end up next to each other. The rest is a single pass that cuts the list into runs: keep adding words to the current group while the next word has the same signature, and start a new group when it differs.
The cost is dominated by the sort. Building a key for a word of length L costs O(L log L), Python builds each key once, and comparing two keys takes O(L). Sorting n words therefore takes roughly O(n * L * log L) for the keys plus O(n * log n * L) for the comparisons, which fits inside the bound the statement gives. The final pass calls sorted twice per word, which adds O(n * L * log L) and does not change the total.
Another common approach puts each word into a dictionary under its sorted letters and returns the dictionary's values. It avoids sorting the list and is faster, but this lesson practises the sort-then-scan pattern, which also applies to other grouping problems.
Step by step
- Sort the list in place with
strings.sort(key=...). Thekeyfunction receives one word and returns what to sort by. Here that isstr(sorted(word)), the word's letters in alphabetical order turned into a string. Anagrams have equal keys, so they become neighbours. - Create
result, an empty list that will hold the finished groups. - Create
currentGroup, an empty list for the group being built. - Loop over the indices with
range(len(strings)). An index is needed because each word is compared with the next one. - Append
strings[i]tocurrentGroup. After sorting, a word always belongs with the group under construction. - Detect the end of a group. A group ends at the last word, or when the next word has different sorted letters. The last-index test comes first on purpose:
orstops as soon as the left side is true, sostrings[i + 1]is never read past the end of the list. - Store the group and start a new one. Append
currentGrouptoresult, then assign a new empty list tocurrentGroup. - Return
resultonce the loop is over.
The solution in Python
class Solution:
def groupAnagrams(self, strings: List[str]) -> List[List[str]]:
strings.sort(key = lambda word: str(sorted(word)))
result = []
currentGroup = []
for i in range(len(strings)):
currentGroup.append(strings[i])
if i == len(strings) - 1 or sorted(strings[i]) != sorted(strings[i + 1]):
result.append(currentGroup)
currentGroup = []
return result
A few Python details are worth knowing:
sorted(word)works on a string. A string is a sequence of characters, sosorted("tea")returns a new list['a', 'e', 't']. It does not return a string, which is why the lesson wraps it instr()for the key.list.sort()returnsNone. It sorts in place, sostrings = strings.sort(...)would replace the list withNone. This also means the caller's list is reordered. Usesorted(strings, key=...)if you need the original order kept.- The sort is stable. Words with equal keys keep their original relative order, so within a group
eat,tea,atestay in the order they appeared in the input. - Rebind, don't clear.
currentGroup = []makes a new list and leaves the one insideresultalone.currentGroup.clear()would empty the same list object thatresultalready holds, and the answer would be full of empty lists. For the input["eat", "tea", "tan"]that bug returns[[], []]. - Comparing lists.
sorted(a) != sorted(b)compares two lists element by element, so it is true exactly when the two words are not anagrams.
Complexity
Time: O(n * log n * L * log L). The sort does O(n log n) comparisons of keys of length O(L) and builds n keys at O(L log L) each. The loop makes n iterations, each with two calls to sorted at O(L log L). The total is within the bound in the statement.
Space: O(n * L). The sort keeps one key per word while it runs, and each key has a size proportional to L. The groups in result hold references to the same strings, so they add only O(n) references.
Edge cases and common mistakes
- Empty list. The loop never runs and the method returns
[]. - A single word. The first iteration is also the last index, so the method returns
[['a']]for["a"]. - Empty strings. The key of
""is"[]", so all empty strings form one group.[""]returns[['']]. - Repeated words. Equal words are anagrams of each other:
["abc", "bca", "abc"]returns one group of three. - Reading past the end. Testing
sorted(strings[i]) != sorted(strings[i + 1])beforei == len(strings) - 1raisesIndexErroron the last word. - Forgetting the final group. A loop that only closes a group when the next word differs never stores the last one. The last-index test handles that.
- Sorting by the word itself.
strings.sort()putsate,bat,eatin alphabetical order and does not bring anagrams together.
Testing
["eat", "tea", "tan", "ate", "nat", "bat"]gives three groups:['bat'],['eat', 'tea', 'ate']and['tan', 'nat'], in that order.[]gives[].[""]gives[['']].["a"]gives[['a']].["abc", "bca", "abc"]gives[['abc', 'bca', 'abc']].
