Home » Interview Questions » String Interview Questions » Print all anagrams together in a sequence of words

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

READ  Valid Number

 

 

How useful was this post?

Click on a star to rate it!

Average rating / 5. Vote Count

No votes so far! Be the first to rate this post.

As you found this post useful...

Follow us on social media!

We are sorry that this post was not useful for you!

Let us improve this post!

Tell us how we can improve this post?

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions