Given an array of strings
strs, group the anagrams together. You can return the answer in any order. An anagram is a word formed by rearranging the letters of another word, using all the original letters exactly once.Example
strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
Output: [["eat", "tea", "ate"], ["tan", "nat"], ["bat"]]
“eat”, “tea”, and “ate” are anagrams of each other (same letters rearranged). “tan” and “nat” are anagrams. “bat” has no anagram partner in the list.
The trick is finding a canonical form that all anagrams share. Sort each string alphabetically — all anagrams produce the same sorted string. Use this sorted string as a hashmap key, and group all original strings that map to the same key together.
Why this works
All anagrams are made of the exact same letters, just rearranged. If you sort each string alphabetically, anagrams collapse into the same string. Use that sorted string as a hashmap key to group them together.
Step by step
- Sort each string — this creates a canonical form that all anagrams share (e.g., “eat” and “tea” both become “aet”).
- Use the sorted string as a hashmap key — all words that are anagrams of each other will map to the same key.
- Append the original word — store the unsorted original under its sorted key so you can return the groups at the end.
- Return all groups — extract the hashmap values, where each value is a list of anagrams.
Time: O(n * k * log k)
Space: O(n * k)
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
Map<String, List<String>> groups = new HashMap<>();
for (String s : strs) {
char[] chars = s.toCharArray();
Arrays.sort(chars); // canonical form for anagram matching
String key = new String(chars);
groups.computeIfAbsent(key, k -> new ArrayList<>()).add(s);
}
return new ArrayList<>(groups.values());
}
}
class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
unordered_map<string, vector<string>> groups;
for (const string& s : strs) {
string key = s;
sort(key.begin(), key.end()); // anagrams produce the same sorted key
groups[key].push_back(s);
}
vector<vector<string>> result;
for (auto& [key, group] : groups) {
result.push_back(move(group));
}
return result;
}
};
def groupAnagrams(strs: list[str]) -> list[list[str]]:
groups = {}
for s in strs:
key = ''.join(sorted(s)) # anagrams produce the same sorted key
if key not in groups:
groups[key] = []
groups[key].append(s) # group under shared key
return list(groups.values())