Description
Partition lowercase words into groups that contain exactly the same letters. Group order is irrelevant.
Solution
def group_anagrams(strs):
groups = {}
for word in strs:
key = ''.join(sorted(word))
groups.setdefault(key, []).append(word)
return list(groups.values())Examples
Inputs are positional arguments. Trees use level-order arrays; linked lists use value arrays. Design problems list operations in order.
Example 1
- Input
[["ab","ba","cat"]]- Output
[["ab","ba"],["cat"]]
ab and ba share a sorted key; cat does not.
Example 2
- Input
[[""]]- Output
[[""]]
The empty word forms one group.
Example 3
- Input
[["a","b","a"]]- Output
[["a","a"],["b"]]
The repeated a words stay together.
Approach
Use the sorted letters as a dictionary key and collect matching words.
Time & space
O(n k log k) time; O(n k) space including keys and output, for n words of maximum length k.