Given a sequence of words, print all anagrams together | Set 1 | GeeksforGeeks
Given an array of words, print all anagrams together. For example, if the given array is {“cat”, “dog”, “tac”, “god”, “act”}, then output may be “cat tac act dog god”.
Time Complexity: Let there be N words and each word has maximum M characters. The upper bound is O(NMLogM + MNLogN).
Step 2 takes O(NMLogM) time. Sorting a word takes maximum O(MLogM) time. So sorting N words takes O(NMLogM) time. step 3 takes O(MNLogN) Sorting array of words takes NLogN comparisons. A comparison may take maximum O(M) time. So time to sort array of words will be O(MNLogN).
Related: Given a sequence of words, print all anagrams togethe
Read full article from Given a sequence of words, print all anagrams together | Set 1 | GeeksforGeeks
Given an array of words, print all anagrams together. For example, if the given array is {“cat”, “dog”, “tac”, “god”, “act”}, then output may be “cat tac act dog god”.
A simple method is to create a Hash Table. Calculate the hash value of each word in such a way that all anagrams have the same hash value. Populate the Hash Table with these hash values. Finally, print those words together with same hash values. A simple hashing mechanism can be modulo sum of all characters. With modulo sum, two non-anagram words may have same hash value. This can be handled by matching individual characters.
Take two auxiliary arrays, index array and word array. Populate the word array with the given sequence of words. Sort each individual word of the word array. Finally, sort the word array and keep track of the corresponding indices. After sorting, all the anagrams cluster together. Use the index array to print the strings from the original array of strings.
Take two auxiliary arrays, index array and word array. Populate the word array with the given sequence of words. Sort each individual word of the word array. Finally, sort the word array and keep track of the corresponding indices. After sorting, all the anagrams cluster together. Use the index array to print the strings from the original array of strings.
struct
Word
{
char
* str;
// to store word itself
int
index;
// index of the word in the original array
};
// structure to represent duplicate array.
struct
DupArray
{
struct
Word* array;
// Array of words
int
size;
// Size of array
}
// Create a DupArray object that contains an array of Words
struct
DupArray* createDupArray(
char
* str[],
int
size)
{
// Allocate memory for dupArray and all members of it
struct
DupArray* dupArray =
(
struct
DupArray*)
malloc
(
sizeof
(
struct
DupArray) );
dupArray->size = size;
dupArray->array =
(
struct
Word*)
malloc
( dupArray->size *
sizeof
(
struct
Word) );
// One by one copy words from the given wordArray to dupArray
int
i;
for
(i = 0; i < size; ++i)
{
dupArray->array[i].index = i;
dupArray->array[i].str = (
char
*)
malloc
(
strlen
(str[i]) + 1 );
strcpy
(dupArray->array[i].str, str[i] );
}
return
dupArray;
}
void
printAnagramsTogether(
char
* wordArr[],
int
size)
{
// Step 1: Create a copy of all words present in given wordArr.
// The copy will also have orignal indexes of words
struct
DupArray* dupArray = createDupArray(wordArr, size);
// Step 2: Iterate through all words in dupArray and sort individual words.
int
i;
for
(i = 0; i < size; ++i)
qsort
(dupArray->array[i].str,
strlen
(dupArray->array[i].str),
sizeof
(
char
), compChar);
// Step 3: Now sort the array of words in dupArray
qsort
(dupArray->array, size,
sizeof
(dupArray->array[0]), compStr);
// Step 4: Now all words in dupArray are together, but these words are
// changed. Use the index member of word struct to get the corresponding
// original word
for
(i = 0; i < size; ++i)
printf
(
"%s "
, wordArr[dupArray->array[i].index]);
}
Step 2 takes O(NMLogM) time. Sorting a word takes maximum O(MLogM) time. So sorting N words takes O(NMLogM) time. step 3 takes O(MNLogN) Sorting array of words takes NLogN comparisons. A comparison may take maximum O(M) time. So time to sort array of words will be O(MNLogN).
Related: Given a sequence of words, print all anagrams togethe
Read full article from Given a sequence of words, print all anagrams together | Set 1 | GeeksforGeeks