Given an array of strings strs, group together the words that are anagrams of each other (they use exactly the same letters the same number of times, like "eat" and "tea"). Return the groups in any order, and the words inside a group in any order.
Example 1
Input: strs = ["eat","tea","tan","ate","nat","bat"]
Output: [["bat"],["nat","tan"],["ate","eat","tea"]]
"eat", "tea" and "ate" share the letters a, e, t. "tan" and "nat" share a, n, t.
Example 2
Input: strs = [""]
Output: [[""]]
Constraints
- 1 <= strs.length <= 10^4
- 0 <= strs[i].length <= 100
- strs[i] has only lowercase English letters
Hints
Frequently asked at: Amazon, Meta, Microsoft, Uber, Goldman Sachs
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
Comparing every pair of words is O(n^2 * k). Instead, give every word a signature that is identical for all its anagrams, then bucket by signature with a hash map. Sorting the letters is the simplest signature (O(k log k) per word). A tuple of 26 letter counts is O(k) per word and is a good follow-up.
Algorithm
- Create a map from key to a list of words.
- For each word, build its key: the letters sorted (or the 26 counts).
- Append the word to
map[key]. - Return all the lists in the map.
Time:
O(n * k log k), where k is the longest word lengthSpace: O(n * k)Interview tip: If you use letter counts as the key in Java, build a string like "1#0#2#..." with separators; without them, counts like 1,11 and 11,1 collide.
class Solution: def groupAnagrams(self, strs: List[str]) -> List[List[str]]: groups = defaultdict(list) for s in strs: key = ''.join(sorted(s)) # same for every anagram groups[key].append(s) return list(groups.values())Ctrl + Enter runs the examples