String anagram

In this post I would be discussing a method to test whether two words (strings) are anagrams of each other or not. Two words are anagrams of each other if the result of rearranging the letters of a word to produce a new word, using all the original letters exactly once; for example orchestra can be rearranged into carthorse.

The easiest or rather the first approach which usually comes in the minds of students is to store the letters of each word into an array and compare the two arrays after sorting them in ascending or descending order. The approach would obviously give correct output but the logic is not good in terms of efficiency due to sorting requirement.

Another approach is to take a single dimension integer array of size twenty six. The idea is to use each element of the array for one of the twenty six alphabets (ignoring the cases) . For each occurrence of a letter in the first word we would increment the corresponding array element once and for each occurrence of a letter in the second word we would decrement the corresponding array element once. This way all the element should be zero in case the two words are anagrams of each other. The Java program to test for string anagrams using the above logic would be as follows:

class StringAnagram{
    public static boolean isAnagram( String a, String b ){
        int length1, length2;
        length1 = a.length();
        length2 = b.length();
        if( length1 != length2 ) return false;
        int freq[] = new int[ 26 ];
        char ch1, ch2;
        for( int i = 0; i < length1 ; i++ ){
            ch1 = Character.toUpperCase( a.charAt( i ) );
            ch2 = Character.toUpperCase( b.charAt( i ) );
            if( Character.isLetter( ch1 ) && Character.isLetter( ch2 ) ){
                freq[ ch1 - 'A' ]++;
                freq[ ch2 - 'A' ]--;
            }
        }
        for( int n: freq ){
            if( n != 0 ) return false;
        }
        return true;
    }
    public static void main( String args[] ){
        System.out.println( isAnagram( "orchestra", "carthorse" ) );
        System.out.println( isAnagram( "Creative", "Reactive" ) );
        System.out.println( isAnagram( "Paternal", "Parental" ) );
        System.out.println( isAnagram( "Admirer", "Married" ) );
        System.out.println( isAnagram( "abcd", "abde" ) );
    }
}

The above program uses enhance for-statement on line number 11. Please refer to my earlier post “Enhanced for loop“, for the details of enhanced for-statement. As usual, the main function has purposely been kept to minimum and its expected that students will write appropriate input/output statements as per the requirement.

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.