[Program] How to Check if Two Strings are Anagrams in C?
Before writing code to check if two strings are anagrams in C, let’s understand- what is the anagram of the string?
What is Anagram of the string?
An anagram of the string is the string, obtained by rearranging the letters of the source string.
Example:
Source String: csestack Anagram of source String: cesstack
The second and third letters of the source string are altered, giving an anagram of the string.
Properties of Anagram String:
- One string may have multiple anagrams.
- Every string is anagram if itself.
- If one string is the anagram of other string, both the strings have equal length. This is the first condition you should check for anagrams.
In C, you can check the length of the string using the strlen() function.
Program to Check if Two Strings are Anagrams in C
There are two approaches to check if the two strings are anagrams of each other or not.
1. by using Quick Sort
- Sort the String using quicksort (both strings)
- After sorting, check if two strings are identical or not
- If two strings are identical then these two strings are anagrams of each other.
- If not identical, these two strings are not anagrams of each other.
#include<stdio.h>
#include<stdbool.h>
#include<string.h>
/* Function prototype
for sorting a given string using quick sort */
void quickSort(char *nArr, int nSI, int nEI);
/* function to check
whether two strings are anagram of each other */
bool checkAnagram(char *strTest1, char *strTest2)
{
int i =0;
// Get lengths of both strings
int nLen1 = strlen(strTest1);
int nLen2 = strlen(strTest2);
// If length of two strings are different,
// these are not anagram
if (nLen1 != nLen2)
return false;
// Sort both strings using quick sort
quickSort (strTest1, 0, nLen1 - 1);
quickSort (strTest2, 0, nLen2 - 1);
// Compare both the sorted strings
for (i = 0; i < nLen1; i++)
if (strTest1[i] != strTest2[i])
return false;
return true;
}
// Following functions
//(exchange and partition are needed for quickSort)
void swapElement(char *a, char *b)
{
char temp;
temp = *a;
*a = *b;
*b = temp;
}
//Partition string into two string using pivot element
int partitionPivot(char nArr[], int nSI, int nEI)
{
char x = nArr[nEI];
int i = (nSI - 1);
int j;
for (j = nSI; j <= nEI - 1; j++)
{
if(nArr[j] <= x)
{
i++;
swapElement(&nArr[i], &nArr[j]);
}
}
swapElement(&nArr[i + 1], &nArr[nEI]);
return (i + 1);
}
/* Quick Sort Implementation
nArr[] : int Array to be sorted
nSI : Starting index of String
nEI : Ending index of String
nPI : Partitioning index (Pivot Index)
*/
void quickSort(char nArr[], int nSI, int nEI)
{
int nPI;
if(nSI < nEI)
{
nPI = partitionPivot(nArr, nSI, nEI);
quickSort(nArr, nSI, nPI - 1);
quickSort(nArr, nPI + 1, nEI);
}
}
int main()
{
char strTest1[] = "csestack";
char strTest2[] = "cesstack";
if (checkAnagram(strTest1, strTest2) )
printf("The two strings are anagram of each other");
else
printf("The two strings are not anagram of each other");
return 0;
}Output:
The two strings are an anagram of each other
For practice, you can solve the problem using any other popular sorting algorithms.
2. by counting each elements
- Create two arrays of size 26 to save elements count for each letter
- Scan first string and count number of times each unique element is repeated. Save count for each letter in the first array
- Repeat the same procedure for the second string.
- Match the two array to check the count for each unique element.
- If it is the same for both strings, two strings are an anagram of each other.
- If there is a mismatch for any unique element count, these two strings are not an anagram of each other.
#include<stdio.h>
#include<stdbool.h>
#include<string.h>
# define NO_OF_CHARS 26
/* function to check whether
two strings are anagram of each other */
bool checkAnagram(char *strTest1, char *strTest2)
{
// Create two count arrays and initialize all values as 0
int nCount1[NO_OF_CHARS] = {0};
int nCount2[NO_OF_CHARS] = {0};
int i=0;
if (strlen(strTest1) != strlen(strTest2))
return false;
// For each character in input strings,
// increment count in
// corresponding count array
//97 is ascii value of 'a'
for (i = 0; strTest1[i] && strTest2[i]; i++)
{
nCount1[strTest1[i]-97]++;
nCount2[strTest2[i]-97]++;
}
// Compare count arrays
for (i = 0; i < NO_OF_CHARS; i++)
if (nCount1[i] != nCount2[i])
return false;
return true;
}
/* Driver program to test to pront printDups*/
int main()
{
char strTest1[] = "csestack";
char strTest2[] = "stackcse";
if (checkAnagram(strTest1, strTest2))
printf("The two strings are anagram of each other");
else
printf("The two strings are not anagram of each other");
return 0;
}Output:
The two strings are anagram of each other.
This is one of the coding questions asked in the interview. If you are preparing for the job, practice solving these coding interview questions.
This is all about the program to check if two strings are anagrams in C. If you find any other better way of solving the same problem, let’s discuss it in the comment.
Comments
Anand
The Coding style is absolutely awesome ans easy to understand..I like this code ..
Aniruddha Chaudhari
Thanks, Anand.