Coding Daily

Problem Description

Given an array of strings, group all anagrams together. Anagrams are words that contain the same characters but in a different order. The groups should maintain the order of their appearance in the original array.

Example:

Input: arr[] = ["act", "god", "cat", "dog", "tac"]
Output: [["act", "cat", "tac"], ["god", "dog"]]
Explanation: The anagram groups are:
- ["act", "cat", "tac"]: These are anagrams of each other.
- ["god", "dog"]: These are anagrams of each other.

Solution Code

import java.util.*;

class Solution {
    public ArrayList<ArrayList<String>> anagrams(String[] arr) {
        // Create a map to store groups of anagrams
        Map<String, ArrayList<String>> map = new HashMap<>();

        for (String word : arr) {
            // Sort the characters of the word to create a key
            char[] charArray = word.toCharArray();
            Arrays.sort(charArray);
            String sortedWord = new String(charArray);

            // Add the word to the corresponding group in the map
            if (!map.containsKey(sortedWord)) {
                map.put(sortedWord, new ArrayList<>());
            }
            map.get(sortedWord).add(word);
        }

        // Convert the map values to a list of lists
        ArrayList<ArrayList<String>> result = new ArrayList<>(map.values());

        return result;
    }
}

Hint

Use a hash map to group words by their sorted character representation. This ensures that all anagrams are grouped together.

Approach Name

Hash Map with Sorted Keys

Intuition

Anagrams have the same characters but in a different order. By sorting the characters of each word, we can create a unique key for all anagrams of that word. Using a hash map, we can group words with the same sorted key together.

Algorithm

Initialize a hash map to store groups of anagrams.
Iterate through each word in the array:
- Sort the characters of the word to create a key.
- Add the word to the corresponding group in the map using the sorted key.
Convert the values of the map (groups of anagrams) into a list of lists.
Return the result.

Test Input

act god cat dog tac

Complexity Analysis

Time Complexity: O(n * m log m), where n is the number of words and m is the maximum length of a word. Sorting each word takes O(m log m), and we do this for n words.
Space Complexity: O(n * m), where n is the number of words and m is the maximum length of a word. The space is used to store the groups of anagrams in the hash map.

This solution efficiently groups anagrams using a hash map and sorted keys, ensuring optimal performance for the given constraints.

Print Anagrams Together