Home
Aptitude
Categories


Home » Interview coding problems/challenges

Checking Anagrams (check whether two string is anagrams or not)



Checking Anagrams: In the following we are going to learn how to check whether two string is anagrams or not?
Submitted by Radib Kar, on November 19, 2018

Problem statement: Given two strings, check whether two given strings are anagram of each other or not. An anagram of a string is another string that contains same characters, only the order of characters can be different.

For example, "act" and "cat" are anagram of each other.

Solution

Algorithm:

Anagram means both the string contains the same set of character, only their orders are different. Thus, in both the string the frequency of each letter must be the same if they are an anagram of each other. Thus our algorithm checks and compare frequency of each letter in both the strings.

  1. The strings to be anagram of each other, their length must be same.
  2. Let n1 be the length of first string & n2 be the length of second string.
    If (n1!=n2)
    	Strings are not anagram. Return.
    Else
    Proceed to step2.
    
  3. Initialize two arrays of length 26 to store frequency of characters in each string.
  4. array1[26]={0}, array2[26]={0};
    //for the first string
    For i=1:n1 //n1 be the length of first string
    	// for each letter of the string their corresponding
    	array1[string1[i]-'a']++; 
    //frequencies are being stored
    
    End for loop
    
    //for the second string
    For i=1:n2 //n2 be the length of second string
    	// for each letter of the string their corresponding
    	array2[string2[i]-'a']++; 
    //frequencies are being stored
    
    End for loop
    
  5. Comparison step
  6. Compare the frequency of each letter in both the strings
    If 
    all the letter in both of the string have same frequency (number of occurrence)
    Then they are anagrams of each other
    Else
    They are not anagrams of each other
    
  7. Print result and return.



C++ program to check whether two string is anagrams or not

#include <bits/stdc++.h>
using namespace std;

int anagram(string s1,string s2){
	int array1[26]={0},array2[26]={0};
	//if string lengths are different
	if(s1.length()!=s2.length())
		return 0; //they are not anagrams
	//for string1
	for(int i=0;s1[i]!='\0';i++){
		//storing frequency for each letter in the string   
		array1[s1[i]-'a']++;     
	}

	//for string2
	for(int i=0;s2[i]!='\0';i++){
		//storing frequency for each letter in the string     
		array2[s2[i]-'a']++;   
	}
	//comparison step
	for(int i=0;i<26;i++){
		// if any letter has different no of occurence, 
		// then strings are not anagrams
		if(array1[i]!=array2[i]) 
			return 0;
	}

	return 1;// else they are anagrams
}
int main()
{
	int n;
	string s1,s2;

	//input the strings
	cout<<"enter string1\n";
	cin>>s1;
	cout<<"enter string2\n";
	cin>>s2;

	if(anagram(s1,s2))
		printf("strings are anagrams of each other\n");
	else
		printf("strings are not anagrams of each other\n");

	return 0;
}

Output

First run:
enter string1
includehelp
enter string2
cnldeehpiul
strings are anagrams of each other 

Second run:
enter string1
includehelp
enter string2
helpincludr
strings are not anagrams of each other 

Explanation:

In the first output,

String1 ='includehelp'
String2='cnldeehpiul'
So, in the first string there is:
one 'I', one 'n', one 'c', two 'l', one 'u', one 'd', two 'e', one 'h' & one 'p'
in the second string there is:
one 'c', one 'n', two 'l', one 'd', two 'e', one 'h' & one 'p', one 'i' &one 'u'
Thus they are anagrams.

But in the second output,

The second string contains 'r' which is not in the first string, thus they are not anagrams.






Comments and Discussions

Ad: Are you a blogger? Join our Blogging forum.





Languages: » C » C++ » C++ STL » Java » Data Structure » C#.Net » Android » Kotlin » SQL
Web Technologies: » PHP » Python » JavaScript » CSS » Ajax » Node.js » Web programming/HTML
Solved programs: » C » C++ » DS » Java » C#
Aptitude que. & ans.: » C » C++ » Java » DBMS
Interview que. & ans.: » C » Embedded C » Java » SEO » HR
CS Subjects: » CS Basics » O.S. » Networks » DBMS » Embedded Systems » Cloud Computing » Machine learning » CS Organizations » Linux » DOS
More: » Articles » Puzzles » News/Updates

© https://www.includehelp.com some rights reserved.