Group Anagrams Together

The idea behind this approach is that two or more than two strings are anagrams if and only if their sorted strings are equal. So we will use a HashMap, let’s say “anagramGroup”, where each key is a sorted string, and the key will be mapping to the list of indices from the given list of strings that form a group of anagrams. This means that if we sort the strings at those indices, we will get the sorted string that is the key for this list of indices in the hashmap. 

The steps are as follows:

1. Define a HashMap, let’s say “anagramsGroups”. The key of the HashMap will be a string and the value will be an array/list of integers that will store the index numbers of the string corresponding to the key.
2. Iterate through the given strings, let’s say we are currently at index ‘i’.
   1. Store the current string in a temporary variable, let’s say “temp”.
   2. Sort the “temp” string and insert ‘i’ to the array corresponding to the “temp” string as the key of the HashMap.
3. Iterate through the HashMap and group all strings at indexes which belong to the same key of the HashMap.

The key idea behind this approach is that we can transform each string into a string representing the character count. We will use an array “frequency", of size 26 such that each element of the array represents the number of a’s, b’s, c’s and so on… We will be using these frequencies to create a string, delimited by ‘#’ characters that we will use as a key for our HashMap.

For example :

str=”abbccc”, will be “#1#2#3#0#0#0#0…#0”, where there are 26 entries total with delimited by ‘#’.

Steps are as follows :

1. Make a HashMap let’s say “anagramGroups” where the key of the string will be generated by transforming the array “frequency” into a string delimited by ‘#’, and the key will be mapping to the list of indices from the given list of strings.  The list of indices of each key will represent the indices of the strings which belong to the same group i.e. all the strings present at the indices of a particular list will be anagrams of one another
2. Iterate over given the list/array of strings. For each string in the list/array of strings:
   1. Store the frequency of character of the strings in the array “frequency”.
   2. Generate the key with the frequencies of characters, delimited by ‘#’. Let’s say “key”.
   3. Insert index of the current string into the HashMap corresponding to the “key”.
3. Once we are done with all the strings in the given list/array of the strings, the list of indices of each key will be representing all the indices of the strings which are anagrams to one another. So we will iterate through the value of our HashMap and group all the strings corresponding to the indices in the given array/list of strings for a particular key.

The idea is to sort each string and insert it into the trie. Each node of trie will have an array to store the indexes of the string ending at that node. Using a trie will improve the access time of the elements when compared to HashMap, hence it will be more efficient than using a HashMap.

The structure of the trie class will be:

class TrieNode
{
public:
    TrieNode *children[26];
    vector<int> index;


    TrieNode()
    {
        for (int i = 0; i < 26; i++)
        {
            children[i] = NULL;
        }
    }
    ~TrieNode()
    {
        for (int i = 0; i < 26; i++)
        {
            if (children[i] != NULL)
            {
                delete children[i];
            }
        }
        index.clear();
        index.resize(0);
    }
};

The array “children” stores the pointers to the children nodes of the current node

The steps are as follows :

1. Define a trie class which has pointers to the children nodes and an additional array as a member to store the indices of strings.
2. Iterate through all the strings.
   1. Store the current string in a temporary variable, let’s say “temp”.
   2. Sort the string “temp”.
   3. Insert the string “temp” into the trie.
   4. Also, push the index of the string in the “index” array of the node of the trie where the last character of the string is stored.
3. Now we will traverse all the nodes of the trie and for each node of the trie, we will group all strings which end at one node.
   1. Define a function traversal(curr) to traverse the trie. Here, “curr” denotes the current node.
   2. Iterate through “curr->index” and group all the strings ending at the current node.
   3. Iterate through the “children” array and recursively traverse the trie.