Problem Statement

Given an array of strings, return all groups of strings that are anagrams. The groups must be created in order of their appearance in the original array. Look at the sample case for clarification.

Example 1:

Input:
N = 5
words[] = {act,god,cat,dog,tac}
Output:
god dog
act cat tac
Explanation:
There are 2 groups of
anagrams "god", "dog" make group 1.
"act", "cat", "tac" make group 2.

Example 2:

Input:
N = 3
words[] = {no,on,is}
Output:
no on
is
Explanation:
There are 2 groups of
anagrams "no", "on" make group 1.
"is" makes group 2.

**Your Task:**The task is to complete the function Anagrams() that takes a list of strings as input and returns a list of groups such that each group consists of all the strings that are anagrams.

Expected Time Complexity: O(N*|S|*log|S|), where |S| is the length of the strings.

Expected Auxiliary Space: O(N*|S|), where |S| is the length of the strings.

**Constraints:**1<=N<=100

Problem Link

Print Anagrams Together | Practice | GeeksforGeeks

Code

// The idea here is store the sorted words into the Trie and where the word ends 
// i.e wordend = true we will store all the anagrams corresponding to that stored word 
struct TrieNode {
    char data;
    vector<string> anagrams;
    bool wordend;
    TrieNode *child[26];
    
    TrieNode (char d)
    {
        data = d;
        wordend = false;
        for(int i=0;i<26;i++)
        child[i] = NULL;
    }
    
};
TrieNode *root = NULL;

void initialize()
{
    root = new TrieNode('/');
}

void insert(string str)
{
    TrieNode *curr = root;
    string org = str;
    sort(str.begin(),str.end());
    for(int i=0;i<str.size();i++)
    {
        int index = str[i]-'a';
        if(!curr->child[index])
        curr->child[index] = new TrieNode(str[i]);
        
        curr = curr->child[index];
    }
    curr->wordend = true;
    curr->anagrams.push_back(org);
}
void dfs(TrieNode *curr,vector<vector<string>> &res,int index)
{
    if(!curr->child[index])
    return;
    
    if(curr->child[index]->wordend)
    {
        res.push_back(curr->child[index]->anagrams);
        return;
    }
    curr = curr->child[index];
    
    for(int i=0;i<26;i++)
     dfs(curr,res,i);
}
vector<vector<string> > Anagrams(vector<string>& string_list) 
{
     initialize();
     
     for(string word:string_list)
     insert(word);
     
     vector<vector<string>> res;
     
     for(int i=0;i<26;i++)
     dfs(root,res,i);
     return res;
}