Group Anagrams medium

Problem Statement

Given an array of strings strs, group the anagrams together. You can return the answer in any order.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Example 1:

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

Example 2:

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

Steps

1. Create a HashMap: We'll use a HashMap to store the anagrams. The key will be a sorted string representation of each word (since anagrams have the same letters, just rearranged), and the value will be a list of strings that are anagrams of that key.

2. Iterate through the input array: For each string in the input array strs:

   • Sort the string alphabetically.
   • Use the sorted string as the key in the HashMap.
   • If the key exists, add the original (unsorted) string to the list associated with that key.
   • If the key doesn't exist, create a new entry in the HashMap with the sorted string as the key and a new list containing the original string as the value.

3. Extract the values: Finally, extract all the values (lists of anagrams) from the HashMap and return them as a list of lists.

Explanation

The core idea is to use a canonical representation of each string to identify anagrams. Sorting the characters of each string provides a consistent way to represent anagrams, regardless of the order of characters. The HashMap efficiently groups strings based on their sorted representations.

Code

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);

            if (!anagramMap.containsKey(sortedStr)) {
                anagramMap.put(sortedStr, new ArrayList<>());
            }
            anagramMap.get(sortedStr).add(str);
        }

        return new ArrayList<>(anagramMap.values());
    }
}

Complexity

• Time Complexity: O(M * N * log N), where N is the average length of strings and M is the number of strings. This is dominated by the sorting operation within the loop (O(N * log N) for each string).
• Space Complexity: O(M * N) in the worst case, where all strings are anagrams of each other. This is because the HashMap might store all strings in a single list. In the best-case scenario (no anagrams), it would be O(M).