Problem
Given an array of strings strs, group the anagrams together. Two strings are anagrams if they contain the same characters with the same frequencies, but possibly in a different order.The grouped lists may be returned in any order.
Example(s)
Consider the following example(s) to understand the expected input and output.Input
strs = ["eat","tea","tan","ate","nat","bat"] Output
[[eat, tea, ate], [tan, nat], [bat]] Solution
This solution uses a HashMap to group words based on a common key.For each string, its characters are sorted alphabetically to produce a canonical representation. Since all anagrams generate the same sorted string, it can be used as the key in the map.
The HashMap stores a list of strings for each sorted key. As each word is processed, it is added to the corresponding list, and finally all grouped values are returned as the result.
public List<List<String>> groupAnagrams(String[] strs) {
Map<String, List<String>> group = new HashMap<>();
for (String s : strs) {
String key = sort(s);
group.computeIfAbsent(key, k -> new ArrayList<>()).add(s);
}
return new ArrayList<>(group.values());
}
private String sort(String s) {
char[] chars = s.toCharArray();
Arrays.sort(chars);
return new String(chars);
}
Complexity
Let n be the number of strings and k be the maximum length of a string.Sorting each string takes
O(k log k), and this is performed for all n strings, resulting in an overall time complexity of O(n × k log k). The extra space complexity is
O(n × k) for storing the grouped strings and their keys.