28. Group Anagrams

Given an array of strings strs, group the anagrams together. You can return the answer in any order. An anagram is a word formed by rearranging the letters of another word, using all original letters exactly once.

Input: strs = ["eat","tea","tan","ate","nat","bat"]
Output: [["bat"],["nat","tan"],["ate","eat","tea"]]

Input: strs = [""]
Output: [[""]]

Input: strs = ["a"]
Output: [["a"]]

Problem Breakdown:

1. Create a hash map where the key is the sorted version of each string (anagrams produce the same sorted string) and the value is a list of original strings.

• groups = {}

2. For each string, sort its characters to create a canonical key. All anagrams will produce the same key.

• for s in strs:
      key = tuple(sorted(s))

3. Add the original string to the list for that key. If the key does not exist, create a new list.

•     if key not in groups:
          groups[key] = []
      groups[key].append(s)

4. Return all values from the hash map as the grouped anagrams.

• return list(groups.values())

Summary:

Use sorted character tuples as hash map keys to group anagrams. All anagrams share the same sorted form. Collect strings by their sorted key and return the grouped values.

Time and Space Complexity:

Time Complexity: O(n * k log k) - where n is the number of strings and k is the maximum string length (sorting each string).

Space Complexity: O(n * k) - storing all strings in the hash map.

Python Solution:

def groupAnagrams(strs):
    groups = {}
    for s in strs:
        key = tuple(sorted(s))
        if key not in groups:
            groups[key] = []
        groups[key].append(s)
    return list(groups.values())

JavaScript Solution:

var groupAnagrams = function(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 Array.from(groups.values());
};

Java Solution:

class Solution {
    public List> groupAnagrams(String[] strs) {
        Map> 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());
    }
}