Group Anagrams - Java Solution

1. Introduction

In this post, we tackle the "Group Anagrams" problem, an interesting challenge that involves string manipulation and categorization. Anagrams are words or phrases formed by rearranging the letters of a different word or phrase, using all the original letters exactly once. The goal is to group all anagrams together from a given list of strings.

Problem

Given an array of strings strs, the task is to group the anagrams together. The function should return the grouped anagrams in any order.

2. Solution Steps

1. Create a hash map to store groups of anagrams, where the key is a sorted string, and the value is a list of strings that are anagrams.

2. Iterate through each string in strs:

a. Sort the characters of the string.

b. Use the sorted string as the key and add the original string to the corresponding list in the hash map.

3. The hash map's values will be the groups of anagrams.

4. Return a list of these groups.

3. Code Program

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class GroupAnagrams {
    public static void main(String[] args) {
        String[] strs = {"eat", "tea", "tan", "ate", "nat", "bat"};
        System.out.println(groupAnagrams(strs)); // Test the function
    }

    // Function to group anagrams
    public static List<List<String>> groupAnagrams(String[] strs) {
        if (strs == null || strs.length == 0) {
            return new ArrayList<>();
        }
        Map<String, List<String>> map = new HashMap<>();
        for (String s : strs) {
            char[] characters = s.toCharArray();
            Arrays.sort(characters);
            String key = new String(characters);
            if (!map.containsKey(key)) {
                map.put(key, new ArrayList<>());
            }
            map.get(key).add(s);
        }
        return new ArrayList<>(map.values());
    }
}

Output:

[["bat"], ["nat", "tan"], ["ate", "eat", "tea"]]

Explanation:

1. groupAnagrams: This function groups anagrams from the array strs.

2. It uses a hash map map where each key is a sorted string, and the value is a list of strings that are anagrams of each other.

3. The function iterates through each string in strs, sorts its characters, and uses the sorted string as a key to group the anagrams.

4. If the key does not exist in map, it initializes a new list. The original string is then added to the list corresponding to the sorted key.

5. The function returns a list of lists, where each inner list contains strings that are anagrams of each other.

6. This approach efficiently groups anagrams by using sorted strings as keys, ensuring that all anagrams have the same key and are thus grouped together.