Group Anagrams

Leetcode Problem: Group Anagrams

Objective:

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.

Pattern: Arrays and Hashing

Approach:

1. Create a 2D list for the result.
2. Create a HashMap: key = sorted word, value = list of anagrams.
3. Iterate through the input string array and sort the input.
4. If the sorted input is not in hashmap or edge case where the sorted input equals the non-sorted input then add the sorted input as the key and the non-sorted input as an anagram.
5. If the sorted input already exists as a key in the hashmap, then get the sorted key and add the non-sorted input into the anagram list.
6. Iterate through the hashmap and add each anagram list into the result list. Return result.

Big-O Notation:

Time Complexity: O(m * nlog(n))
We have iterate n times for each string.
We sort each string using Arrays.sort() which is O(n log(n)).

Space Complexity: O(n * m)
We use additional data structures for storage.
We have a 2D list to store the result.
We have a hashmap to store elements.

Code:

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        // input: string array 
        // output: 2D list 
        List<List<String>> result = new ArrayList<List<String>>();

        Map <String, List<String>> hashMap = new HashMap<>();

        for(String str : strs){
            char [] array = str.toCharArray();
            Arrays.sort(array);

            String sortStr = str.valueOf(array);

            // edge case if current == key then add to key. 
            if(sortStr == str || !hashMap.containsKey(sortStr)){
                List <String> anagram = new ArrayList<>();
                anagram.add(str);
                hashMap.put(sortStr, anagram);
            } else {
                hashMap.get(sortStr).add(str);
            }
        }

        // add anagram list into result 
        for(String s : hashMap.keySet()){
            result.add(hashMap.get(s));
        }

        return result;
    }
}