Interview challenge · medium · string, hash-map, sorting
Group Anagrams
The challenge
Given a list of strings, group the anagrams together: words made of the same letters in any order. Groups keep the order in which they first appear.
Example
["eat", "tea", "tan", "ate", "nat", "bat"]
-> [["eat", "tea", "ate"], ["tan", "nat"], ["bat"]]
[""] -> [[""]]Idea: two words are anagrams exactly when their letters, sorted, give the same string. Use that sorted string as a key and append each word to the group of its key: a hash map in Python, a short list of keys in C. Time O(n·k log k) for n words of length k.
The solution
# Group Anagrams - ayotl.dev
def group_anagrams(words):
groups = {}
for w in words:
# anagrams share the same sorted key
key = "".join(sorted(w))
groups.setdefault(key, []).append(w)
return list(groups.values())
print(group_anagrams(["eat", "tea", "tan",
"ate", "nat", "bat"]))
print(group_anagrams([""]))
$ python3 group_anagrams.py
[['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]
[['']]