Print all anagrams together in a sequence of words

Given a sequence of words, print all anagrams together.

Example

Input : words[] =[“apt, are, ear, tap, art, rat”]
Output : apt, tap, are, ear, art, rat

Here, (apt, tap), (are, ear), (art, rat) are anagrams.

Time complexity : O(NMlogM + MNlogN)

Algorithm

a. Create two auxiliary arrays.

b. One is index array(index[]) to store indexes, other is word array to store words.

c. Sort each individual word in the sequence(sort characters).

d. Sort the word array and keep track of indexes(corresponding).

e. Use index array to print the strings.

Algorithm working

Input :

Index[] = [0, 1, 2, 3, 4, 5]
words[] =[“apt, are, ear, tap, art, rat”]
sort individual words,
Index[] = [0, 1, 2, 3, 4, 5]
words[] = [“apt, aer, aer, apt, art, art”]
sort the word array and update index array,
Index[] = [1, 2, 0, 3, 4, 5]
words[] = [“aer, aer, apt, apt, art, art”]
print based on index array, Output: apt, tap, are, ear, art, rat

C++ Program

#include <bits/stdc++.h>

using namespace std;

struct Word
{
    //string is word and index is its index in the array
    char* string;
    int index; 
};
 
//Array of words and its size
struct WordArray
{
    struct Word* array;
    int size;
};
 
int CompareChars(const void* a, const void* b)
{
    return *(char*)a - *(char*)b;
}

int CompareStrings(const void* a, const void* b)
{
    struct Word* a1 = (struct Word *)a;
    struct Word* b1 = (struct Word *)b;
    return strcmp(a1->string, b1->string);
}
 
void AnagramsTogether(char* words[], int size)
{
    //Copy words into word array 
    struct WordArray* wordArray =(struct WordArray*) malloc( sizeof(struct WordArray) );
    wordArray->size = size;
    wordArray->array =(struct Word*) malloc( wordArray->size * sizeof(struct Word) );
    int k;
    for (k = 0; k < size; ++k)
    {
        wordArray->array[k].index = k;
        wordArray->array[k].string = (char*) malloc( strlen(words[k]) + 1 );
        strcpy(wordArray->array[k].string, words[k] );
    }
    //sort each word of the words array
    int i;
    for (i = 0; i < size; ++i)
    {
       qsort(wordArray->array[i].string,strlen(wordArray->array[i].string), sizeof(char), CompareChars);
    }
    //sort words of the word array
    qsort(wordArray->array, size, sizeof(wordArray->array[0]), CompareStrings);
    //print words based on there indexes
    for (i = 0; i < size; ++i)
    {
        cout<<words[wordArray->array[i].index]<<", ";
    }
}
 
//Main function
int main()
{
    char* words[] = {"ear", "pat", "rat", "are", "art", "tap"};
    int size = sizeof(words) / sizeof(words[0]);
    AnagramsTogether(words, size);
    return 0;
}

Try It

 

 

Translate »