anagram check Algorithm
The anagram check algorithm is a technique used to determine if two given strings are anagrams of each other. An anagram is a word or phrase formed by rearranging the letters of another word or phrase, like "debit card" and "bad credit". The algorithm works by comparing the occurrences of characters in both strings and ensuring they have the same frequency distribution. The core idea behind this algorithm is that two strings are anagrams if and only if they consist of the same characters with the same frequency.
There are multiple ways to implement the anagram check algorithm, but one common approach is to use a hash table or a dictionary to store the frequency count of characters in each string. First, iterate through the characters in the first string and increment the respective count in the hash table. Then, iterate through the characters in the second string and decrement the respective count in the hash table. Finally, check if all the values in the hash table are zero, indicating that the two strings have the same character frequency distribution and are therefore anagrams. Another approach is to sort the characters in both strings and compare the sorted strings for equality. If the sorted strings are equal, then the original strings are anagrams. This method, although simpler, may have a higher time complexity due to the sorting step.
//
// C/C++ program to check whether two strings are anagrams
// of each other
//
// The All ▲lgorithms Project
//
// https://allalgorithms.com/strings
// https://github.com/allalgorithms/cpp
//
// Contributed by: Tushar Kanakagiri
// Github: @tusharkanakagiri
//
#include <stdio.h>
#include <string.h>
/* Function prototype for string a given string using
quick sort */
void quickSort(char *arr, int si, int ei);
/* function to check whether two strings are anagram of
each other */
bool areAnagram(char *str1, char *str2)
{
// Get lenghts of both strings
int n1 = strlen(str1);
int n2 = strlen(str2);
// If length of both strings is not same, then they
// cannot be anagram
if (n1 != n2)
return false;
// Sort both strings
quickSort(str1, 0, n1 - 1);
quickSort(str2, 0, n2 - 1);
// Compare sorted strings
for (int i = 0; i < n1; i++)
if (str1[i] != str2[i])
return false;
return true;
}
// Following functions (exchange and partition are needed
// for quickSort)
void exchange(char *a, char *b)
{
char temp;
temp = *a;
*a = *b;
*b = temp;
}
int partition(char A[], int si, int ei)
{
char x = A[ei];
int i = (si - 1);
int j;
for (j = si; j <= ei - 1; j++)
{
if (A[j] <= x)
{
i++;
exchange(&A[i], &A[j]);
}
}
exchange(&A[i + 1], &A[ei]);
return (i + 1);
}
/* Implementation of Quick Sort
A[] --> Array to be sorted
si --> Starting index
ei --> Ending index
*/
void quickSort(char A[], int si, int ei)
{
int pi; /* Partitioning index */
if (si < ei)
{
pi = partition(A, si, ei);
quickSort(A, si, pi - 1);
quickSort(A, pi + 1, ei);
}
}
/* Driver program to test to print printDups*/
int main()
{
char str1[] = ""; //String 1
char str2[] = ""; //String 2
if (areAnagram(str1, str2))
printf("The two strings are anagram of each other");
else
printf("The two strings are not anagram of each other");
return 0;
}
