Problem

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

Definition

Anagram Definition

Examples

For example, suppose that we have the following strings:

Example 1:

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

Example 2:

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

Example 3:

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

Solution

Method 1 - Brute Force

For each word in the array, initiate another loop to compare it with other words, identifying and grouping any anagrams. Time complexity - O(n^2)

Method 2 - Group Words Based on Hash Value

One straightforward approach is to construct a Hash Table. Compute hash values for each word such that anagrams yield identical hash values. Populate the Hash Table with these values. However, devising an appropriate hash function can be challenging. Instead, consider the following method that utilizes a count array.

Method 3 - Use the Map of Frequency Array 🏆

This method works in case of lower case english letters only. Here are the steps:

  • For each word in the array, generate a frequency array (256 characters, though the code below uses 26 characters for lowercase words).
  • If this frequency array is already present, an anagram has been found; otherwise, add the frequency array to the map.

Code

Java
class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<>();
        for (String str : strs) {
            char[] arr = new char[26];
            for (int i = 0; i < str.length(); i++) {
                arr[str.charAt(i) - 'a']++;
            }

            String countString = new String(arr);
            map.putIfAbsent(countString, new ArrayList<String>());

            map.get(countString).add(str);
        }

		List<List<String>> ans = new ArrayList<List<String>>();
        ans.addAll(map.values());
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n * m) where average length of string is m and array length is n
  • 🧺 Space complexity: `O(n/m * 26)``

Method 4 - Sort the words individually and then group them

We can also do following:

  1. Convert each string into a character array, sort it, and then convert it back into a string to get the sorted version.
  2. Check if the sorted version exists in the map. If not, create a new list for that sorted version.
  3. Add the original string to the corresponding list in the map.

Dry Run

Let us understand the steps with following input Sequence of Words:

strs = ["cat", "dog", "tac", "god", "act"]
Processing all words
  • Process cat ⇨ map = { act: [cat]}
  • Process dog ⇨ map = { act: [cat], dgo: [dog]}
  • Process tac ⇨ map = { act: [cat, tac], dgo: [dog]}
  • Process god ⇨ map = { act: [cat, tac], dgo: [dog, god]}
  • Process act ⇨ map = { act: [cat, tac, act], dgo: [dog, god]}
Final Answer

We can now convert map values to list.

Code

Java
     public 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[] charArray = s.toCharArray();
             Arrays.sort(charArray);
             String sorted = new String(charArray);
             if (!map.containsKey(sorted)) {
                 map.put(sorted, new ArrayList<>());
             }
             map.get(sorted).add(s);
         }
 
         return new ArrayList<>(map.values());
     }

Complexity

  • ⏰ Time complexity: O(n ** m log m)
  • 🧺 Space complexity: O(n * m)

Method 5 - Use the Trie

We can use Trie Data Structure, and add [[Array-based Trie Implementation]]. Then, we can take following steps:

  • Sort the word by character and insert the words in trie
  • Store the sorted word in trie, and at each leaf store the list of original words
  • Finally go through all trie leaves, and get list of original words

Code

Java
class Solution {
    static class Trie {
        static class TrieNode {
            private boolean isLeaf;
            private TrieNode[] children = new TrieNode[26];
            private List<String> words = new ArrayList<>(); // Store words at the leaf nodes
        }

        private TrieNode root;

        /** Initialize the Trie. */
        public Trie() {
            this.root = new TrieNode();
        }

        /** Inserts a word into the trie. */
        public void insert(String word, String originalWord) {
            TrieNode curr = this.root;

            for (char c : word.toCharArray()) {
                int idx = c - 'a';
                if (curr.children[idx] == null) {
                    curr.children[idx] = new TrieNode();
                }
                curr = curr.children[idx];
            }

            curr.isLeaf = true;
            curr.words.add(
                originalWord); // Add the original word at the leaf node
        }

        // Function to traverse the Trie and collect all anagrams
        public void collectAnagrams(TrieNode node, List<List<String>> result) {
            if (node == null)
                return;

            if (node.isLeaf) {
                result.add(new ArrayList<>(node.words));
            }

            for (TrieNode child : node.children) {
                if (child != null) {
                    collectAnagrams(child, result);
                }
            }
        }
    }
    
    public List<List<String>> groupAnagrams(String[] strs) {
        if (strs == null || strs.length == 0) {
            return new ArrayList<>();
        }

        Trie trie = new Trie();

        for (String s : strs) {
            char[] charArray = s.toCharArray();)
            Arrays.sort(charArray);
            String sortedWord = new String(charArray);
            trie.insert(sortedWord, s);
        }
        List<List<String>> ans = new ArrayList<>();
        collectAnagrams(this.root, ans);
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n * m log m)
  • 🧺 Space complexity: O(n * m)