Wednesday, September 18, 2013

How to check if two strings are anagrams of each other

Anagram of a word is nothing but rearrangement of it's letters to form another word.

For example 'listen' is an anagram of 'silent' and 'enlist'.

We have to write a function to check if two given strings are anagrams are not.

We can solve this problem in two different ways. The first way is to sort the two strings and compare them. If they are equal, they are anagrams; otherwise they are not. The intuition behind this is by sorting the letters in the string, it forms a unique pattern. All anagrams must transform to this unique pattern when they are sorted.



For example when we sort the letters in the string 'listen' or 'silent' it becomes
'eilnst' 

Here is the Java function which implements the first method. Here I have used separate strings to hold the sorted sequence so that the original strings are not modified. If the original strings can be modified, we can avoid using the extra String variables.

 public static boolean areAnagrams(String strFirst, String strSecond )
    {
        char [] charArray = strFirst.toCharArray();
        Arrays.sort(charArray);
        String strFirstSort = new String( charArray );
        charArray = strSecond.toCharArray();
        Arrays.sort(charArray);
        String strSecondSort = new String( charArray );

        return strFirstSort.equals(strSecondSort);
    }

Method#2:
The second method is to count the letters in both the strings and match the counts. If the letter count of both the strings is same, then we can conclude that they are anagrams.


In the following Java implementation we do not count the frequencies of letters in both the strings, but we calculate the counts for just one string.

public static boolean areAnagrams(String strFirst, String strSecond )
    {
        //Assume ASCII charset of size 256 alphabets
        int[] charCount = new int[256];

        getCharCount(strFirst,charCount);

        for( int i = 0; i < strSecond.length(); i++ )
        {
            char ch = strSecond.charAt(i);
            // If count of ch is more in second string, return false
            if( charCount[ch] <= 0 )
                return false;
            else
                charCount[ch]--;
        }

        for( int i = 0; i < 256; i++ )
        {
            if( charCount[i] > 0 )
                return false;
        }
        return true;
    }
    public static void getCharCount(String strInput, int[] charCount)
    {
        for( int i = 0; i < strInput.length(); i++ )
        {
            charCount[ strInput.charAt(i)]++;
        }
    }

Then we iterate through the characters of the second string, we try to decrement the frequency of each character. If we found a zero, that means that particular character has appeared more number of times in the second string, then we can say that they are not anagrams. Otherwise we decrement the count of that character.

Finally we check the count array if they have any non-zero entries. If they are anagrams, we have all zero entries in count array. 

Note: We have considered the space also as a significant character in the above programs. So 'school master' can not be anagram of 'the classroom'  even though they contain same letters. Also the input strings are case-sensitive.