Given an array of words, print all anagrams together.
Input : {“cat”, “dog”, “tac”, “god”, “act”}Output : {“cat”, “tac”, “act”, ‘”dog”, “god”}
Making a hash table is an easy way. Determine the hash value of every word so that the hash value of every anagram is the same. Add these hash values to the Hash Table. Lastly, use the same hash values to print those words together. The modulo sum of all characters’ ASCII values can serve as a basic hashing technique. Two non-anagram words may have the same hash value when modulo sum is used. Individual characters must be matched in order to manage this.
Here’s another way to print all the anagrams at once. Consider the word array, index array, and two auxiliary arrays. Add the specified word sequence to the word array. The word array’s individual words are sorted. Lastly, sort the word array while monitoring the associated indices. All of the anagrams group together after sorting. To print the strings from the initial array of strings, use the index array.
Let’s use the following word sequence as input to better understand the steps:
"cat", "dog", "tac", "god", "act"
1) Create two auxiliary arrays index[] and words[]. Copy all given words to words[] and store the original indexes in index[]
index[]: 0 1 2 3 4 words[]: cat dog tac god act
2) Sort individual words in words[]. Index array doesn’t change.
index[]: 0 1 2 3 4 words[]: act dgo act dgo act
3) Sort the words array. Compare individual words using strcmp() to sort
index: 0 2 4 1 3 words[]: act act act dgo dgo
4) All anagrams come together. But words are changed in the words array. To print the original words, take the index from the index array and use it in the original array. We get
"cat tac act dog god"
The aforesaid algorithm’s implementations are shown below. Both index and word arrays are stored in an array of structure “Word” in the program that follows. Another structure that holds an array of “Word” structures is called Dupray.
C
// A C program to print all anagrams together
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// structure for each word of duplicate array
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;
}
// Compare two characters. Used in qsort() for sorting an
// array of characters (Word)
int compChar(const void* a, const void* b)
{
return *(char*)a - *(char*)b;
}
// Compare two words. Used in qsort() for sorting an array
// of words
int compStr(const void* a, const void* b)
{
struct Word* a1 = (struct Word*)a;
struct Word* b1 = (struct Word*)b;
return strcmp(a1->str, b1->str);
}
// Given a list of words in wordArr[],
void printAnagramsTogether(char* wordArr[], int size)
{
// Step 1: Create a copy of all words present in given
// wordArr. The copy will also have original 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]);
}
// Driver program to test above functions
int main()
{
char* wordArr[] = { "cat", "dog", "tac", "god", "act" };
int size = sizeof(wordArr) / sizeof(wordArr[0]);
printAnagramsTogether(wordArr, size);
return 0;
}C++
// A C++ program to print all anagrams together
#include <bits/stdc++.h>
#include <string.h>
using namespace std;
// structure for each word of duplicate array
class Word {
public:
char* str; // to store word itself
int index; // index of the word in the original array
};
// structure to represent duplicate array.
class DupArray {
public:
Word* array; // Array of words
int size; // Size of array
};
// Create a DupArray object that contains an array of Words
DupArray* createDupArray(char* str[], int size)
{
// Allocate memory for dupArray and all members of it
DupArray* dupArray = new DupArray();
dupArray->size = size;
dupArray->array
= new Word[(dupArray->size * sizeof(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
= new char[(strlen(str[i]) + 1)];
strcpy(dupArray->array[i].str, str[i]);
}
return dupArray;
}
// Compare two characters. Used in qsort() for
// sorting an array of characters (Word)
int compChar(const void* a, const void* b)
{
return *(char*)a - *(char*)b;
}
// Compare two words. Used in qsort()
// for sorting an array of words
int compStr(const void* a, const void* b)
{
Word* a1 = (Word*)a;
Word* b1 = (Word*)b;
return strcmp(a1->str, b1->str);
}
// Given a list of words in wordArr[],
void printAnagramsTogether(char* wordArr[], int size)
{
// Step 1: Create a copy of all words present in given
// wordArr. The copy will also have original indexes of
// words
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)
cout << wordArr[dupArray->array[i].index] << " ";
}
// Driver program to test above functions
int main()
{
char* wordArr[] = { "cat", "dog", "tac", "god", "act" };
int size = sizeof(wordArr) / sizeof(wordArr[0]);
printAnagramsTogether(wordArr, size);
return 0;
}
// This is code is contributed by rathbhupendraJava
// A Java program to print all anagrams together
import java.util.Arrays;
import java.util.Comparator;
public class GFG {
// class for each word of duplicate array
static class Word {
String str; // to store word itself
int index; // index of the word in the
// original array
// constructor
Word(String str, int index)
{
this.str = str;
this.index = index;
}
}
// class to represent duplicate array.
static class DupArray {
Word[] array; // Array of words
int size; // Size of array
// constructor
public DupArray(String str[], int size)
{
this.size = size;
array = new Word[size];
// One by one copy words from the
// given wordArray to dupArray
int i;
for (i = 0; i < size; ++i) {
// create a word Object with the
// str[i] as str and index as i
array[i] = new Word(str[i], i);
}
}
}
// Compare two words. Used in Arrays.sort() for
// sorting an array of words
static class compStr implements Comparator<Word> {
public int compare(Word a, Word b)
{
return a.str.compareTo(b.str);
}
}
// Given a list of words in wordArr[],
static void printAnagramsTogether(String wordArr[],
int size)
{
// Step 1: Create a copy of all words present
// in given wordArr. The copy will also have
// original indexes of words
DupArray dupArray = new DupArray(wordArr, size);
// Step 2: Iterate through all words in
// dupArray and sort individual words.
int i;
for (i = 0; i < size; ++i) {
char[] char_arr
= dupArray.array[i].str.toCharArray();
Arrays.sort(char_arr);
dupArray.array[i].str = new String(char_arr);
}
// Step 3: Now sort the array of words in
// dupArray
Arrays.sort(dupArray.array, new 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)
System.out.print(
wordArr[dupArray.array[i].index] + " ");
}
// Driver program to test above functions
public static void main(String args[])
{
String wordArr[]
= { "cat", "dog", "tac", "god", "act" };
int size = wordArr.length;
printAnagramsTogether(wordArr, size);
}
}
// This code is contributed by Sumit GhoshPython
# A Python program to print all anagrams together
# structure for each word of duplicate array
class Word(object):
def __init__(self, string, index):
self.string = string
self.index = index
# Create a DupArray object that contains an array
# of Words
def createDupArray(string, size):
dupArray = []
# One by one copy words from the given wordArray
# to dupArray
for i in xrange(size):
dupArray.append(Word(string[i], i))
return dupArray
# Given a list of words in wordArr[]
def printAnagramsTogether(wordArr, size):
# Step 1: Create a copy of all words present in
# given wordArr.
# The copy will also have original indexes of words
dupArray = createDupArray(wordArr, size)
# Step 2: Iterate through all words in dupArray and sort
# individual words.
for i in xrange(size):
dupArray[i].string = ''.join(sorted(dupArray[i].string))
# Step 3: Now sort the array of words in dupArray
dupArray = sorted(dupArray, key=lambda k: k.string)
# 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 word in dupArray:
print wordArr[word.index],
# Driver program
wordArr = ["cat", "dog", "tac", "god", "act"]
size = len(wordArr)
printAnagramsTogether(wordArr, size)
# This code is contributed by BHAVYA JAINC#
// A C# program to print all anagrams together
using System;
using System.Linq;
// structure for each word of duplicate array
class Word {
public string Str; // to store word itself
public int Index; // index of the word in the original array
}
// structure to represent duplicate array.
class DupArray {
public Word[] Array; // Array of words
public int Size; // Size of array
}
public class GFG {
// Create a DupArray object that contains an array of Words
static DupArray CreateDupArray(string[] str, int size)
{
// Allocate memory for dupArray and all members of it
var dupArray = new DupArray();
dupArray.Size = size;
dupArray.Array = new Word[dupArray.Size];
// One by one copy words from the given wordArray to
// dupArray
for (var i = 0; i < size; i++) {
dupArray.Array[i] = new Word();
dupArray.Array[i].Index = i;
dupArray.Array[i].Str = str[i];
}
return dupArray;
}
// Compare two words. Used in OrderBy()
// for sorting an array of words
static int CompStr(Word a, Word b)
{
return string.Compare(new string(a.Str.OrderBy(c => c).ToArray()), new string(b.Str.OrderBy(c => c).ToArray()));
}
// Given a list of words in wordArr[],
static void PrintAnagramsTogether(string[] wordArr, int size)
{
// Step 1: Create a copy of all words present in given
// wordArr. The copy will also have original indexes of
// words
var dupArray = CreateDupArray(wordArr, size);
// Step 2: Iterate through all words in
// dupArray and sort individual words .
// Step 3: Now sort the array of words in dupArray
Array.Sort(dupArray.Array, CompStr);
// Step 3: 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
foreach (var word in dupArray.Array)
{
Console.Write(wordArr[word.Index] + " ");
}
}
// Driver program to test above functions
static public void Main(string[] args)
{
var wordArr = new string[] { "cat", "dog", "tac", "god", "act" };
var size = wordArr.Length;
PrintAnagramsTogether(wordArr, size);
}
}
// This code is contributed by Prasad Kandekar(prasad264)JavaScript
// A JavaScript program to print all anagrams together
// structure for each word of duplicate array
class Word {
constructor(string, index) {
this.string = string;
this.index = index;
}
}
// Create a DupArray object that contains an array
// of Words
function createDupArray(string, size) {
let dupArray = [];
// One by one copy words from the given wordArray
// to dupArray
for (let i = 0; i < size; i++) {
dupArray.push(new Word(string[i], i));
}
return dupArray;
}
// Given a list of words in wordArr[]
function printAnagramsTogether(wordArr, size) {
// Step 1: Create a copy of all words present in
// given wordArr.
// The copy will also have original indexes of words
let dupArray = createDupArray(wordArr, size);
// Step 2: Iterate through all words in dupArray and sort
// individual words.
for (let i = 0; i < size; i++) {
dupArray[i].string = dupArray[i].string.split("").sort().join("");
}
// Step 3: Now sort the array of words in dupArray
dupArray = dupArray.sort((a, b) => a.string.localeCompare(b.string));
// 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 (let word of dupArray) {
console.log(wordArr[word.index]);
}
}
// Driver program
let wordArr = ["cat", "dog", "tac", "god", "act"];
let size = wordArr.length;
printAnagramsTogether(wordArr, size);
// This code is contributed by prasad264Results:
Cat tac act dog god
Time Complexity: Assume that there are N words with a maximum of M characters per word. O(NMLogM + MNLogN) is the upper bound.
O(NMLogM) time is required for step 2. Word sorting requires a maximum of O(MLogM) time. Thus, it takes O(NMLogM) time to sort N-words. O(MNLogN) is taken in step 3. Sorting a word array requires NLogN comparisons. Maximum O(M) time may be required for a comparison. Thus, O(MNLogN) will be the time required to sort a word array.
Complexity of space: O(N*M)