ISourceCode

Make the frequent cases fast and the rare case correct

Program to find if a string is an anagram of another string ( implemented in C++ and Java)

If you are here looking for a C# solution check this article.

A string can be rearranged to create a new string. For example Old West Action is an anagram of Clint Eastwood.

The following programs have inputs that are case sensitive . A feature that can be improved.Also sentences can be taken as input for example : Old West Action.But, the other string must contain equal number of spaces of the first string, since Clint Eastwood has a single space the programs wont work. It will work if there is a double space between ‘Clint Eastwood’. This is again a simple feature that can be extended.

For now let us see this working for two individual strings ( as title suggests)

import java.io.*;

public class AnagramFinder
{
  public static boolean anagram(String a, String b) 
  {
        if (a.length() != b.length()) return false;
	int[] alphanum = new int[256];
	int chars = 0; //no of unique characters
	int num_completed_b = 0;
	char[] a_array = a.toCharArray();
	for (char c : a_array) 
	{ // count number of each char in a.
		if (alphanum[c] == 0) ++chars;
		++alphanum[c];
	}
	for (int i = 0; i < b.length(); ++i) 
	{
		int c = (int) b.charAt(i);
		if (alphanum[c] == 0) 
		{ // if you find more of char c in b than in a return false.
			return false;
		}
		--alphanum[c];
		if (alphanum[c] == 0) 
		{
	 	       ++num_completed_b;
			if (num_completed_b == chars) 
			{
				// it’s a match if b has been processed completely
				return i == b.length() - 1;
			}
		}
	}
	return false;
 }
 public static void main (String[] args) {
	System.out.println ("Enter the first string");
	String string1 = "";
	String string2 = "";
	InputStreamReader input1 = new InputStreamReader(System.in);
	BufferedReader reader1 = new BufferedReader(input1);
	try
	{
    		string1 = reader1.readLine();
	}
	catch(Exception e1){}
	System.out.println ("Enter the second string");
	InputStreamReader input2 = new InputStreamReader(System.in);
	BufferedReader reader2 = new BufferedReader(input2);
	try
	{
   		string2 = reader2.readLine();
	}
	catch(Exception e2){}
	boolean value = anagram(string1,string2);
	if(value == true)	
	System.out.println("The string are anagrams of each other");
	else
	System.out.println("The string are NOT anagrams of each other");
 }//end of main
}//end of class

OUTPUT:
laptop:~$ java AnagramFinder
Enter the first string
algo123*!
Enter the second string
!agol321*
The string are anagrams of each other

laptop:~$ java AnagramFinder
Enter the first string
old west action
Enter the second string
clint eastwood
The string are anagrams of each other

oducs@oducs-laptop:~$ java AnagramFinder
Enter the first string
abc
Enter the second string
ABC
The string are NOT anagrams of each other

Below is a C++ version of the program

#include<iostream>
using namespace std;
void Anagramfinder(char *s) 
{
         //Declare and initialize an array of 256 number where each position has its   respective position with respect to 
	// 256 different characters
         int array[256]={0};
         char *s1=s;
          //check till end of string till NULL is encountered
         while(*s!='\0')
         {
           //increment the number of occurance of each char with it equivalent position in the array[256]
           array[(int)*s]+=1;
           s++;
         }
         char ans[100];
         cout<<"\nEnter the string to check for anagram=";
         cin.getline(ans, 100);
         //performing same task done with original input string
         int a[256]={0};
         bool gotit=true; // gotit indicates if its is anagram
         for(int i=0;ans[i]!='\0';i++)
         {
           a[(int)ans[i]]+=1;
         }
         for(int i=0;i<256;i++)
         { 
           if(a[i]!=array[i])
           {
             gotit=false;
             break; 
           }
         }
        //if anagram is present prints is anagram else "is not"
         if(gotit)
           cout<<"\nThe string "<<ans<<" is anagram of"<<s1<<"\n";
         else
           cout<<"\nThe string "<<ans<<" is not anagram of"<<s1<<"\n";
}
int main()
{
         char s[100];
         cout<<"\nEnter the string =";
         cin.getline(s, 100);
         Anagramfinder(s);
         return 0;
}
       

OUTPUT:
laptop:~/code$ ./a.out
Enter the string =algo123*!
Enter the string to check for anagram=!agol321*
The string !agol321* is anagram of algo123*!

laptop:~/code$ ./a.out
Enter the string =algorithms
Enter the string to check for anagram=algo123
The string algo123 is NOT anagram of algorithms

As you can see both these methods employ the strategy of checking if two strings have the identical counts for each unique character

To beat this tedious approach you can also sort the string and see if they are equal. sort(a)==sort(b)

Thanks for reading

15 responses to “Program to find if a string is an anagram of another string ( implemented in C++ and Java)

  1. Arjun January 17, 2011 at 10:05 am

    Its working…!! Thanks mate!

  2. Kishore Ravindran January 19, 2011 at 5:09 am

    Cool.. its ready to use. Adding reference link to the Algorithms (if existing) for which you have written the code would be great…. πŸ™‚

  3. Senthil Kumar D S January 22, 2011 at 12:54 pm

    Very useful sample code. Gracias.

  4. Surendar September 28, 2011 at 6:27 am

    Will this work on the below case :

    String a = aabcd
    String b = abbcd

    The above case is not a anagram. I think it will return true for this case.

    • chinmaylokesh September 28, 2011 at 6:53 am

      labuser@ubuntu:~$ java AnagramFinder
      Enter the first string
      aabcd
      Enter the second string
      abbcd
      The string are NOT anagrams of each other
      labuser@ubuntu:~$

      labuser@ubuntu:~$ ./a.out

      Enter the string =aabcd

      Enter the string to check for anagram=abbcd

      The string abbcd is not anagram ofaabcd
      labuser@ubuntu:~$

  5. shantanu December 20, 2011 at 7:03 am

    I want a code which will give o/p like

    if given string is “India is my country”

    then it will give o/p i=3
    n=2
    d=1
    a=1
    s=1
    m=1
    y=2
    c=1
    o=1
    u=1
    t=1
    r=1

    plz send me this code on my mail id

    • chinmaylokesh February 14, 2012 at 3:53 am

      You are thinking on the lines of Hash tables which is the optimal solution. Use O(nlogn) sorting algorithm to sort the initial string and store the alphabets as keys. O(1) for look up of hash table.
      Its easy to implement hash table. Encourage you do to this πŸ™‚

  6. Pingback: C# – Check if strings are anagrams with NUnit testing « Code through the Looking Glass

  7. Akash September 30, 2012 at 4:14 pm

    Hi,
    Is there any way we can get list of all the anagrams instead of checking if two strings are anagram?
    Eg :-
    Input :- aabc
    Anagrams :-
    abac
    acba

  8. Pingback: C# – LINQ – Check if two strings are Anagrams using Dictionary data structure « Source CO-De-tachment 2702

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: