Understanding the Problem

Given an array of strings strs, our task is to group the strings that are anagrams of each other together and return them as a list of lists.

Approach

To efficiently group anagrams, we can leverage the properties of anagrams. Two strings are anagrams of each other if they have the same characters in the same frequency but in a different order.

We’ll use a HashMap to store the sorted version of each string as the key and the list of original strings as the value. By sorting the characters of each string, we ensure that anagrams will have the same sorted representation.

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        HashMap<String, ArrayList<String>> map = new HashMap<>();
        for (int i = 0; i < strs.length; i++) {
            char[] temp = strs[i].toCharArray();
            Arrays.sort(temp);
            String s = new String(temp);
            if (map.containsKey(s)) {
                map.get(s).add(strs[i]);
            } else {
                map.put(s, new ArrayList<>(Arrays.asList(strs[i])));
            }
        }
        List<List<String>> answer = new ArrayList<>();
        for (Map.Entry<String, ArrayList<String>> mapElement : map.entrySet()) {
            answer.add(mapElement.getValue());
        }
        return answer;
    }
}

Explanation

• We iterate through each string in the input array strs.
• For each string, we sort its characters and use the sorted string as a key in the HashMap.
• If the sorted string already exists in the HashMap, we add the original string to the corresponding list.
• If the sorted string is not present, we create a new ArrayList and add the original string to it, then put it in the HashMap.
• Finally, we iterate through the HashMap and add the lists of anagrams to the result list.

Conclusion

This solution efficiently groups anagrams together in linear time complexity. By leveraging the properties of anagrams and using HashMaps to store and retrieve the groups, we achieve an optimal solution to the problem of grouping anagrams in Java.

https://leetcode.com/problems/group-anagrams/description