The problem
Given an array of strings strs, group together the words that are anagrams of each other — made of exactly the same letters. Return the groups in any order.
Examples
01
- Input
strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
- Output
[["bat"], ["nat", "tan"], ["ate", "eat", "tea"]]
02
- Input
strs = [""]
- Output
[[""]]
Constraints
- 1 ≤ strs.length ≤ 10⁴
- 0 ≤ strs[i].length ≤ 100
- Every string contains only lowercase English letters.
The idea
Two words are anagrams exactly when they contain the same number of each letter. So give every word a “signature”: its 26 letter counts. Anagrams share a signature; nothing else does.
Use the signature as a key in a hash map whose values are lists of words. Each word is counted (length k) and dropped into its list. Sorting each word would also give a signature, but costs k log k per word; counting costs k.
- Time
- O(n · k) — n words, each of length up to k, counted once
- Space
- O(n · k) — the map holds every word
Solution · every language run against every case
class Solution: def groupAnagrams(self, strs: List[str]) -> List[List[str]]: groups = defaultdict(list) # letter counts -> words with those counts for word in strs: count = [0] * 26 for ch in word: count[ord(ch) - ord('a')] += 1 groups[tuple(count)].append(word) return list(groups.values())