Group Anagrams

• Initialize a hash map map where key is a String and value is a List<String>.
• Iterate through each string s in the input array strs.
• Create an integer array count of size 26, initialized to zeros.
• For each character c in s, increment count[c - 'a'].
• Build a key string from the count array. A simple way is to append each count value preceded by a delimiter (e.g., #) to a StringBuilder.
• Use this generated key to store the original string s in the map, creating a new list if the key is new.
• After iterating through all strings, return a new list containing the values of the map.

We use a hash map, similar to the previous approach. However, the key is generated differently. For each string, we compute its character frequency. Since the strings only contain lowercase English letters, we can use an integer array of size 26 for this. After counting, we need to convert this frequency array into a unique, hashable key. A common way is to create a string representation. For example, an array [1, 2, 0, ...] (one 'a', two 'b's) can be converted to a string like "1#2#0#...". We iterate through the input strs. For each string s, we calculate its character count array. We then build a key string from this count array. This key is used to store the original string s in the hash map. Finally, we return the lists of strings from the map's values. This method avoids the O(K log K) sorting cost, replacing it with a linear O(K) scan.

1import java.util.ArrayList;2import java.util.HashMap;3import java.util.List;4import java.util.Map;5 6class Solution {7    public List<List<String>> groupAnagrams(String[] strs) {8        if (strs == null || strs.length == 0) {9            return new ArrayList<>();10        }11        Map<String, List<String>> map = new HashMap<>();12        for (String s : strs) {13            int[] count = new int[26];14            for (char c : s.toCharArray()) {15                count[c - 'a']++;16            }17            18            StringBuilder sb = new StringBuilder();19            for (int i = 0; i < 26; i++) {20                sb.append('#');21                sb.append(count[i]);22            }23            String key = sb.toString();24            25            if (!map.containsKey(key)) {26                map.put(key, new ArrayList<>());27            }28            map.get(key).add(s);29        }30        return new ArrayList<>(map.values());31    }32}

• Initialize an empty list of lists result and a boolean array visited of size n (length of strs).
• Loop through each string strs[i] from i = 0 to n-1.
• If strs[i] has not been visited (visited[i] is false):
  • Create a new list currentGroup and add strs[i] to it.
  • Mark visited[i] as true.
  • Loop through the remaining strings strs[j] from j = i+1 to n-1.
  • If strs[j] has not been visited and is an anagram of strs[i]:
    • Add strs[j] to currentGroup.
    • Mark visited[j] as true.
  • Add currentGroup to the result.
• Return result.

We iterate through the input array strs. For each string strs[i], we start a new group. We then iterate through the rest of the array (j from i+1 to n-1). For each strs[j], we check if it's an anagram of strs[i]. To check for anagrams, we can sort both strings and see if the sorted versions are equal. A visited array is used to mark strings that have been placed into a group, so they are not considered again as the starting point of a new group. This method is straightforward but highly inefficient due to the nested loops and repeated anagram checks.

1import java.util.ArrayList;2import java.util.Arrays;3import java.util.List;4 5class Solution {6    public List<List<String>> groupAnagrams(String[] strs) {7        if (strs == null || strs.length == 0) {8            return new ArrayList<>();9        }10        List<List<String>> result = new ArrayList<>();11        boolean[] visited = new boolean[strs.length];12 13        for (int i = 0; i < strs.length; i++) {14            if (!visited[i]) {15                List<String> currentGroup = new ArrayList<>();16                currentGroup.add(strs[i]);17                visited[i] = true;18                for (int j = i + 1; j < strs.length; j++) {19                    if (!visited[j] && isAnagram(strs[i], strs[j])) {20                        currentGroup.add(strs[j]);21                        visited[j] = true;22                    }23                }24                result.add(currentGroup);25            }26        }27        return result;28    }29 30    private boolean isAnagram(String s1, String s2) {31        if (s1.length() != s2.length()) {32            return false;33        }34        char[] arr1 = s1.toCharArray();35        char[] arr2 = s2.toCharArray();36        Arrays.sort(arr1);37        Arrays.sort(arr2);38        return Arrays.equals(arr1, arr2);39    }40}

• Initialize a hash map map where key is a String and value is a List<String>.
• Iterate through each string s in the input array strs.
• Convert s to a character array charArray.
• Sort charArray.
• Create a new string key from the sorted charArray.
• Retrieve the list of strings for key from the map. If it doesn't exist, create a new list.
• Add the original string s to this list.
• Put the key and the updated list back into the map.
• After the loop, the map's values will contain the grouped anagrams.
• Return a new list constructed from the values of the map.

We create a hash map where keys are sorted strings and values are lists of original strings that correspond to that sorted key. We iterate through the input array strs. For each string, we convert it to a character array, sort the array, and then convert it back to a string. This sorted string serves as the key. We then use this key to add the original string to the corresponding list in the hash map. If the key is not yet in the map, we first create a new empty list for it. After processing all strings, the values of the hash map are the required groups of anagrams. We collect these lists and return them.

1import java.util.ArrayList;2import java.util.Arrays;3import java.util.HashMap;4import java.util.List;5import java.util.Map;6 7class Solution {8    public List<List<String>> groupAnagrams(String[] strs) {9        if (strs == null || strs.length == 0) {10            return new ArrayList<>();11        }12        Map<String, List<String>> map = new HashMap<>();13        for (String s : strs) {14            char[] charArray = s.toCharArray();15            Arrays.sort(charArray);16            String key = new String(charArray);17            if (!map.containsKey(key)) {18                map.put(key, new ArrayList<>());19            }20            map.get(key).add(s);21        }22        return new ArrayList<>(map.values());23    }24}