NeetCode 150: Group Anagrams

Open Table of contents

The Problem
The Approach
My Solution

The Problem

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	Example 2	Example 3
Input: `strs` = [“eat”,“tea”,“tan”,“ate”,“nat”,“bat”] Output: [[“bat”],[“nat”,“tan”],[“ate”,“eat”,“tea”]]	Input: `strs` = [""] Output: [[""]]	Input: `strs` = [“a”] Output: [[“a”]]

The Approach

The goal is to group the elements of strs by anagrams. From Valid Anagrams we found that if the sorted strings are equal, they are valid anagrams of each other.

Thus, the sorted string is the common key for a group of anagrams. Building on this approach, a Map data structure would be apt for this key-value grouping.

Similar to Valid Anagrams, we need to sort the strings (the key) & insert the unsorted strings (the value) into a Map. The List of all the values in the Map would yield the grouped anagrams.

My Solution

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        // If length is 1, create a List of 1 List & add the element.
        if (strs.length == 1) {
            List<List<String>> result = new ArrayList();
            List<String> list1 = new ArrayList<String>();
            list1.add(strs[0]);
            result.add(list1);
            return result;
        }
        // Use a HashMap for fast insertion.
        Map<String, List<String>> resultMap = new HashMap<String, List<String>>();

        // Converts each element to a char[] & sorts it. This is then converted
        // back to a string. This sorted string the identifier (key).
        for (int i = 0; i < strs.length; i++) {
            String current = strs[i];
            char[] charArray = current.toCharArray();

            Arrays.sort(charArray);
            String sortedStrand = new String(charArray);

            // Checks if the Key (sortedStrand) is present, if not a new 
            // key-value pair is created and placed.
            if (!((resultMap.containsKey(sortedStrand)))) {
                List<String> individualList = new ArrayList<String>();
                individualList.add(current);

                resultMap.put(sortedStrand, individualList);
            } else {
                resultMap.get(sortedStrand).add(current);
            }
        }
        // Creates a List of lists using the Values of the Map.
        return new ArrayList<List<String>>(resultMap.values());
    }
}

The first segment checks if strs.length == 1. Then;

result that is an ArrayList that contains type List<String>
list1 that is an ArrayList that contains type String

are initialized. list1 is inserted into result & returned.

The second segment gets the sortedStrand of each element in strs, which acts as the key. The ArrayList of unsorted strings with the same sortedStrand in strs are the values. This key-value pairs are inserted into resultMap which is a HashMap.

An ArrayList that contains type List<String> is initialized where each List is the grouped anagrams & is returned.