Solution Explanation for Group Anagrams

The problem asks to group anagrams together from a given array of strings. Anagrams are words or phrases formed by rearranging the letters of another. The solution involves using a hash table (or dictionary in Python) to efficiently group the anagrams.

Approach 1: Sorting

This approach leverages the fact that anagrams have the same letters, regardless of their order. Therefore, if we sort the letters of each string alphabetically, anagrams will have identical sorted strings.

1. Sort each string: For every string in the input array, we sort its characters in ascending order. This creates a unique key for each group of anagrams.
2. Use a hash table: We use a hash table (dictionary in Python, HashMap in Java, etc.) where the sorted string (the key) maps to a list of strings (the value). This list contains all the original strings that have the same sorted form (i.e., the anagrams).
3. Populate the hash table: We iterate through the input array. For each string, we obtain its sorted form (the key). If the key exists in the hash table, we append the original string to the corresponding list. Otherwise, we create a new entry in the hash table with the sorted string as the key and a new list containing the original string.
4. Return the values: Finally, we extract the values (the lists of anagrams) from the hash table and return them.

Time Complexity: O(n * k * log k), where n is the number of strings and k is the maximum length of a string. Sorting each string takes O(k * log k) time, and we do this for n strings.

Space Complexity: O(n * k) in the worst case, where all strings are unique (no anagrams), resulting in a hash table with n entries, each storing a string of length k.

Approach 2: Character Counting

This approach avoids sorting. It uses character counts as the key for the hash table.

1. Count characters: For each string, we create a count array (or a string representing the counts) to store the frequency of each character (a-z). This array (or string) becomes the key for the hash table.
2. Use a hash table: Similar to Approach 1, we utilize a hash table to map the character count key to a list of strings.
3. Populate the hash table: We iterate through the input array, generate the character count key for each string, and add the string to the corresponding list in the hash table.
4. Return the values: Finally, we extract the values from the hash table and return them.

Time Complexity: O(n * k), where n is the number of strings and k is the maximum length of a string. We iterate through each string once to count characters.

Space Complexity: O(n * k) in the worst case (similar to Approach 1), as each string might be stored in the hash table.

Code Examples (Python, Java, C++)

Approach 1 (Sorting):

Python:

from collections import defaultdict
 
class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        anagram_dict = defaultdict(list)
        for s in strs:
            sorted_s = "".join(sorted(s))
            anagram_dict[sorted_s].append(s)
        return list(anagram_dict.values())
 

Java:

import java.util.*;
 
class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> anagramMap = new HashMap<>();
        for (String str : strs) {
            char[] charArray = str.toCharArray();
            Arrays.sort(charArray);
            String sortedStr = new String(charArray);
            anagramMap.computeIfAbsent(sortedStr, k -> new ArrayList<>()).add(str);
        }
        return new ArrayList<>(anagramMap.values());
    }
}

C++:

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <map>
 
using namespace std;
 
class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        map<string, vector<string>> anagramMap;
        for (string& str : strs) {
            string sortedStr = str;
            sort(sortedStr.begin(), sortedStr.end());
            anagramMap[sortedStr].push_back(str);
        }
        vector<vector<string>> result;
        for (auto const& [key, val] : anagramMap) {
            result.push_back(val);
        }
        return result;
    }
};

Approach 2 (Character Counting): Similar code can be written for Approach 2 in Python, Java, and C++, using character count arrays or strings as keys instead of sorted strings. The core logic remains the same – using a hash table to group strings based on their character counts.