Anagram Program in C | String Anagram Program in C

Anagram Program in C: Two strings are said to be anagrams if they satisfy two conditions, the length of both strings must be equal to each other and second the strings must have the same set of characters.

Example 1:

First String = “hectare” and Second String = “teacher”

Case 1:
Lengths must be equal to each other.
length of “hectare” = 7
length of “teacher” = 7
Case 1 passed.

Case 2:
Set of characters in
hectare {‘h’ , ’e’ , ’c’ , ’t’ , ’a’ , ’r’ , ’e’}
teacher {‘t’ , ’e’ , ’a’ , ’c’ , ’h’ , ’e’, ’r’}

Every character from the first string has a similar character to it in the other string. Case 2 passed.

”teacher” and ”hectare” are anagrams.

Example 2:

First String = “filming” and Second String = “films”
Case 1:
Length of “filming”=7
Length of “films”=5
The lengths of both the strings don’t match thus they cannot be anagrams.

Problem Description

Write a C program that takes two strings as input and checks whether two strings are anagrams.

Problem Solution

1. Take two strings as input.
2. Sort two strings according to their ASCII values.
3. Now compare the two strings. If both are equal, then they are anagrams. Otherwise they are not anagrams.

Note: Join free Sanfoundry classes at Telegram or Youtube

There are several ways to check whether two strings are anagrams or not in C language. Let’s look at the different techniques in detail.

Anagram Program in C using Naive Approach
Anagram Program in C by Hashing with Help of ASCII Value Key

Method 1: Anagram Program in C (Naive Approach)

In the naive approach, we will check whether two strings are anagrams or not.

Example:

Input:
First String = “study”
Second String = “dusty”

Output:
“study” and “dusty” are anagrams.

Program/Source Code

Here is source code of the C Program to check whether two strings are anagrams. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

```
 
```
```
/*
```

 * C Program to Check whether two Strings are Anagrams

```
 */
```
```
 
```
```
#include <stdio.h>
```
```
 
```
```
int find_anagram(char [], char []);
```
```
 
```
```
int main()
```
```
{
```
```
    char array1[100], array2[100];
```
```
    int flag;
```
```
 
```
```
    printf("Enter the string\n");
```
```
    gets(array1);
```
```
    printf("Enter another string\n");
```
```
    gets(array2);
```

    flag = find_anagram(array1, array2);

```
    if (flag == 1)
```

        printf("%s and %s are anagrams.\n", array1, array2);

```
    else
```

        printf(" %s and %s are not anagrams.\n", array1, array2);

```
    return 0;
```
```
}
```
```
 
```

int find_anagram(char array1[], char array2[])

```
{
```

    int num1[26] = {0}, num2[26] = {0}, i = 0;

```
 
```
```
    while (array1[i] != '\0')
```
```
    {
```
```
        num1[array1[i] - 'a']++;
```
```
        i++;
```
```
    }
```
```
    i = 0;
```
```
    while (array2[i] != '\0')
```
```
    {
```
```
        num2[array2[i] -'a']++;
```
```
        i++;
```
```
    }
```
```
    for (i = 0; i < 26; i++)
```
```
    {
```
```
        if (num1[i] != num2[i])
```
```
            return 0;
```
```
    }
```
```
    return 1;
```
```
}
```

Program Explanation

1. Take two strings as input and store them in the arrays array1[] and array2[] respectively.
2. In the function find_anagram() using while statement sort both the arrays. After sorting compare them using for loop.
3. If all the strings are equal then the two strings are anagrams, otherwise they are not anagrams.

Time Complexity: O(n)
As we are only traversing the array at once so we can conclude that the time
complexity of the above program/algorithm is linear.

Space complexity: O(1)

Runtime Test Cases

Testcase 1: The runtime output of the C program to check whether two strings are anagrams is shown below, where the first string is “study” and second string is “dusty”.

Enter the string
study
Enter another string
dusty
"study" and "dusty" are anagrams.

Testcase 2: The runtime output of the C program to check whether two strings are anagrams is shown below, where the first string is “tall” and second string is “all”.

Enter the string
tall
Enter another string
all
"tall" and "all" are not anagrams.

Method 2: Anagram Program in C by Hashing with Help of ASCII Value Key

In this approach, we check whether two strins are anagram or not by hashing with the help of ASCII value key.

ASCII (American Standard Code for Information Interchange) is the most common character encoding format for text data on computers and the internet. Each alphabet, numeric value, special symbol, and space is encoded with a unique ASCII value.

Approach:
1. We will input the string.
2. Find lengths of both the arrays.
3. If the lengths are unequal, it is obvious that they are not anagrams.
4. Two words will be anagram if they have same set of characters, with each characters frequency in first string to be equal to its frequency in the second string.

Program/Source Code

Here is source code of the C Program to check whether two strings are anagrams by hashing with the help of ASCII value. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

```
 
```
```
/*
```

 * C Program to Check whether two Strings are Anagrams using ASCII Value

```
 */
```
```
 
```
```
#include<stdio.h>
```
```
#include<stdlib.h>
```
```
#include<malloc.h>
```

#define M 1000 // Maximum string length to be inputted.

// 256 is the set of possible characters in our string from ASCII value 0 to ASCII value 255

```
#define CHARSET 256
```
```
 
```

int checkanagram(char *array1,int alen,char *array2,int blen)

```
{
```
```
    //case 1 verfication
```
```
    if(alen != blen)
```
```
    {
```
```
        return 0;
```
```
    }
```
```
 
```
```
    // Initialize the hash array.
```
```
    int HashArray[CHARSET]={0};
```

    int ascii; //temporary variable to store the ASCII value of the character.

```
 
```

    // Fill the array with frequencies of character in the string.

```
    for(int i = 0 ; i < alen; i++)
```
```
    {
```

        //ASCII value is the represented as index in the array.

```
        ascii=array1[i];
```

        // value represent the frequency of the character.

        HashArray[ascii]=HashArray[ascii]+1;

```
    }
```
```
 
```

    // Decrease the frequencies once the character is found in the second string.

```
    for(int i =0; i < blen; i++)
```
```
    {
```
```
        ascii=array2[i];
```

        HashArray[ascii]=HashArray[ascii]-1;

        // If a frequency becomes -1 it means that that character is not in second string.

```
        if(HashArray[ascii] == -1)
```
```
        {
```
```
            return 0;
```
```
        }
```
```
    }
```
```
    return 1;
```
```
}
```
```
int getsize(char *str)
```
```
{
```
```
    int i=0;
```
```
    while(str[i] != 0)
```
```
    {
```
```
        i++;
```
```
    }
```
```
    return i;
```
```
}
```
```
int main()
```
```
{
```
```
    char x[M];
```
```
    char y[M];
```
```
 
```

    printf("Enter the First String:\t");

```
    gets(x);
```
```
 
```

    printf("Enter the Second String:\t");

```
    gets(y);
```
```
 
```
```
    int l1=getsize(x);
```
```
    int l2=getsize(y);
```
```
 
```
```
    if(checkanagram(x ,l1 ,y ,l2)){
```

        printf("%s and %s are anagrams",x,y);

```
    }
```
```
    else{
```

        printf("%s and %s are not anagrams",x,y);

```
    }
```
```
    return 0;
```
```
}
```

Program Explanation

1. Initialize the hash array and store the ASCII value of the character.
2. We can store the frequency of characters in a hash table array where index represent the ascii value and hash table array[index] represent the frequency of that character in the string.
3. Before it fills up, the Hash Table will appear like this.

Index of array	Value in the index of array
0	0
1	0
2	0
3	0
4	0
5	0
6	0
\|	0
\|	0
\|	0
\|	0
\|	0
253	0
254	0
255	0

4. Steps to fill the array.

Initialize a temporary variable temp to store ASCII value.
We iterate variable counter the string from 0 to its length.
Store the ASCII value of string1 [counter] in temp variable.
Increase the value of HashTable[temp] by 1, as frequency increases when a new character is introduces.

5. After the filling of the array, we get:
Index of array Value in the index of an array

Index of array	Value in the index of array
0	0
1	0
2	0
3	0
4	5
5	1
6	0
\|	1
\|	0
\|	0
\|	2
\|	0
253	4
254	1
255	0

6. As we can see values are increased as new character are introduced. After that we need to decrease the value once the value in encountered in the second string.
7. For that we iterate the string from 0 to its length, if any values become -1 it means that that character is non common element both the strings.
8. If all the values in the HashTable are 0, then we can assume that all the element are common and have same frequency in both the strings.

Time complexity: O(n)
As we are only traversing the array at once, so we can conclude that the time complexity of the above program/algorithm is linear i.e O(n).

Space complexity: O(length(string1) + length(string2) + 256 +k)
Because we are storing two strings and a hash table with 256 elements/size, the space complexity is O(length (string1) + length (string2) + 256 +k), where K=constant for auxiliary variables.

Runtime Test Cases

Testcase 1: The runtime output of the C program to check whether two strings are anagrams is shown below, where the first string is “Teacher” and second string is “hectare”.

Enter the First String:
teacher
Enter the Second String:
hectare
"teacher" and "hectare" are anagrams.

Testcase 2: The runtime output of the C program to check whether two strings are anagrams is shown below, where the first string is “palindrome” and second string is “dorm”.

Enter the First String:
palindrome
Enter the Second String:
dorm
"palindrome" and "dorm" are not anagrams.

To practice programs on every topic in C, please visit “Programming Examples in C”, “Data Structures in C” and “Algorithms in C”.

« Prev - C Program to Copy One String to Another using Recursion

» Next - C Program to Find the First Capital Letter in a String without Recursion

Related Posts:

Recommended Articles: