Problem
Given an array of strings, group anagrams together. You can return the answer in any order.
Example
Input: ["eat","tea","tan","ate","nat","bat"]
Output: [["bat"],["nat","tan"],["ate","eat","tea"]]Solution
Use sorted string as a hash key. All anagrams produce the same sorted string.
def group_anagrams(strs):
groups = {}
for s in strs:
key = ''.join(sorted(s))
groups.setdefault(key, []).append(s)
return list(groups.values())function groupAnagrams(strs) {
const groups = new Map();
for (const s of strs) {
const key = s.split('').sort().join('');
if (!groups.has(key)) groups.set(key, []);
groups.get(key).push(s);
}
return [...groups.values()];
}vector<vector<string>> groupAnagrams(vector<string>& strs) {
unordered_map<string, vector<string>> groups;
for (string s : strs) {
string key = s;
sort(key.begin(), key.end());
groups[key].push_back(s);
}
vector<vector<string>> result;
for (auto& g : groups) result.push_back(g.second);
return result;
}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);
String key = new String(chars);
groups.computeIfAbsent(key, k -> new ArrayList<>()).add(s);
}
return new ArrayList<>(groups.values());
}Complexity
- Time: O(n * k log k)
- Space: O(n * k)
Explanation
Sorting each string takes O(k log k). For tighter complexity, use a 26-element character count tuple as the key — O(n * k) time.
Comments
Join the discussion. Got a question, found an issue, or want to share your experience?