Algorithm C++ programming Coding

C++ Programming – all pairs of anagrams

C++ Programming - all pairs of anagrams - Algorithm - One simple idea to find whether all anagram pairs is to run two nested loops.

Given an array of strings, find all anagram pairs in the given array.
Example:

Input: arr[] =  {"geeksquiz", "geeksforgeeks", "abcd",
                 "forgeeksgeeks", "zuiqkeegs"};
Output: (geeksforgeeks, forgeeksgeeks), (geeksquiz, zuiqkeegs)

We can find whether two strings are anagram or not in linear time using count array (see method 2 of this).

One simple idea to find whether all anagram pairs is to run two nested loops. The outer loop picks all strings one by one. The inner loop checks whether remaining strings are anagram of the string picked by outer loop. Following is C++ implementation of this simple approach.

C++ Program
#include <iostream>
using namespace std;
#define NO_OF_CHARS 256
 
/* function to check whether two strings are anagram of each other */
bool areAnagram(string str1, string str2)
{
    // Create two count arrays and initialize all values as 0
    int count[NO_OF_CHARS] = {0};
    int i;
 
    // For each character in input strings, increment count in
    // the corresponding count array
    for (i = 0; str1[i] && str2[i];  i++)
    {
        count[str1[i]]++;
        count[str2[i]]--;
    }
 
    // If both strings are of different length. Removing this condition
    // will make the program fail for strings like "aaca" and "aca"
    if (str1[i] || str2[i])
      return false;
 
    // See if there is any non-zero value in count array
    for (i = 0; i < NO_OF_CHARS; i++)
        if (count[i])
            return false;
     return true;
}
 
// This function prints all anagram pairs in a given array of strigns
void findAllAnagrams(string arr[], int n)
{
    for (int i = 0; i < n; i++)
        for (int j = i+1; j < n; j++)
            if (areAnagram(arr[i], arr[j]))
                cout << arr[i] << " is anagram of " << arr[j] << endl;
}
 
 
/* Driver program to test to pront printDups*/
int main()
{
    string arr[] = {"geeksquiz", "geeksforgeeks", "abcd", 
                    "forgeeksgeeks", "zuiqkeegs"};
    int n = sizeof(arr)/sizeof(arr[0]);
    findAllAnagrams(arr, n);
    return 0;
}

Output:

geeksquiz is anagram of zuiqkeegs
geeksforgeeks is anagram of forgeeksgeeks

The time complexity of the above solution is O(n2*m) where n is number of strings and m is maximum length of a string.

READ  C++ Programming - Check if an array can be divided into pairs whose sum is divisible by k

About the author

Venkatesan Prabu

Venkatesan Prabu

Wikitechy Founder, Author, International Speaker, and Job Consultant. My role as the CEO of Wikitechy, I help businesses build their next generation digital platforms and help with their product innovation and growth strategy. I'm a frequent speaker at tech conferences and events.

Add Comment

Click here to post a comment