How to Write a Check Anagram Program in Java

Hey there! In this article, you will learn how to create an anagram program in java. I will show you three different approaches to solve this problem, plus analyzing how efficient every approach is using big o notation.

Big O analysis will help us understand which program is faster and make a better and more efficient memory usage. Plus big o analysis helps you understand how fast your program will be when you pass really large inputs. Additionally, it just takes a few minutes to do. Let’s get started!

What is an Anagram?

The first step when solving a problem is understanding the problem, not only the problem itself but also any edge cases or assumptions you made. In this case, an anagram is two sequences of characters, that contain the same characters but in a different order. To define the problem better there are some points you should clarify:

• Should the anagram check be case sensitive?
• Should it ignore whitespaces

For this example, the answers to those questions are: no, the check is not case sensitive, and yes, it should ignore the whitespaces.

Perfect, now that we understand the problem better, let’s gather a few meaningful examples. These examples can be handy since they will help you test your code, once you complete it.

Anagram examples

Let’s write down some anagram examples:

Example 1 : "New York Times","monkeys write" => Anagram

Example 2 : "McDonald's restaurants",  "Uncle Sam's standard rot" => Anagram

Example 3 : "1 hey 2", " yeh 21 " => Anagram 

Example 4 : "Rocket Boys",  "October Sky" => Anagram

Now that we got some examples, let’s see how to write a java program to make an anagram check.

Approach #1: Sorting

One way to solve this problem is by sorting the characters in alphabetic order. If the sentences are anagrams, after sorting, you will end up with two identical character sequences.

It should be noted you should clean the inputs first, meaning remove the white spaces, since we should ignore them. And also converting all characters to lower case since the check is not case sensitive. See this in action in the example below:

Input => "New York Times","monkeys write"

After cleaning => "newyorktimes","monkeyswrite"

After sorting => "eeikmnorstwy","eeikmnorstwy"

And below, you can see how to translate this approach to Java:

public class Anagrams {
	    public static boolean checkIfAnagrams1(String text1, String text2){
        // Remove whitespaces and uppercase  
        String cleanText1 = text1.replace(" ","").toLowerCase();
        String cleanText2 = text2.replace(" ","").toLowerCase();
        if(cleanText1.length()!=cleanText2.length()) return false;
        
        // Sort characters
        char[] text1Chars = cleanText1.toCharArray();
        char[] text2Chars = cleanText2.toCharArray();
        Arrays.sort(text1Chars);
        Arrays.sort(text2Chars);
          
        // Compare 
        boolean isAnagram = Arrays.equals(text1Chars,text2Chars);
        return isAnagram;
    }
}

Time Efficiency

How fast is the previous approach? The Arrays.sort() is based on the Time Sort algorithm, which means a time complexity of O(n log(n)). And Arrays.equals() has a complexity of O(n), since the worst-case scenario it has to iterate over every array element.

Approach #2: Counting Character

A different approach is counting the character occurrences. If two sentences are anagrams, the character count should be the same for both sentences. Therefore you could have two integer arrays, where you save the count for each character, and lastly, check the arrays are equals.

Or, if you like to save some memory, it is possible to keep the counts in one single array. How? When you find a character in the first sentence, you increment the count and decrease it when you find the same character in the second sentence. If the sentences are an anagram, the count should end up being zero for all characters. Let’s see how that works in action:

Input => "New York Times","monkeys write"

After cleaning => "newyorktimes","monkeyswrite"

                                e i k m n o r s t w y
sentence 1 count(increment) => [2,1,1,1,1,1,1,1,1,1,1] 

                                e i k m n o r s t w y
sentence 2 count(decreasing) => [0,0,0,0,0,0,0,0,0,0,0] 

And below, you can find how to translate this approach into java code:

public class Anagrams {
    public static boolean checkIfAnagrams2(String text1, String text2){

        // Remove whitespaces and uppercase
        String cleanText1 = text1.replace(" ","").toLowerCase();
        String cleanText2 = text2.replace(" ","").toLowerCase();
        if(cleanText1.length()!=cleanText2.length()) return false;

        // Array to keep track of chracter count
        int ALL_POSSIBLE_ASCII_CHARACTER = 256;
        int[] count = new int[ALL_POSSIBLE_ASCII_CHARACTER];
        for(int i=0;i<cleanText1.length();i++){
            count[cleanText1.charAt(i)]++;
            count[cleanText2.charAt(i)]--;
        }

        // If any count is not 0, the sentences are not an anagram
        for(int countForOneCharacter:count){
            if (countForOneCharacter!=0){
                return false;
            }
        }
        return true;
    }
}

The first step was to clean the input sentences just like before, so white spaces and uppercase are ignored. The next step is creating an array where we will keep the counts.

Please note that the counts are indexed using the ASCII corresponding number for each character. Check the character ASCII table. That means, for instance, the count of the character ‘n’ is stored in position 110 of the array.

Finally, to check if the input sentences are anagram, all you need to do is checking that all counts are zero. If any count is different than zero, the function can return false; the sentences are not anagrams.

Time Efficiency

In this case, the code has to iterate over every element of the array to count the occurrences. Therefore the time complexity is O(n).

Approach #3: Checking the sum

The last approach to check anagrams is calculating the sum of all characters. This approach also uses the ASCII table. It will convert each character to its equivalent decimal ASCII number and then sum up all numbers for each sentence. If the sum is the same, it means the two sentences contain the same characters. Therefore anagrams.

Below you can see the java code to achieve this:

public class Anagrams {
public static boolean checkIfAnagrams3(String text1,String text2){

        // Remove whitespaces and uppercase
        String cleanText1 = text1.replace(" ","").toLowerCase();
        String cleanText2 = text2.replace(" ","").toLowerCase();
        if(cleanText1.length()!=cleanText2.length()) return false;

        // Sum up the value of all characters
        int sum1 = 0;
        int sum2 = 0;
        for(int i=0;i<cleanText1.length();i++){
            sum1=sum1+(int)cleanText1.charAt(i);
            sum2=sum2+(int)cleanText2.charAt(i);
        }
        return sum1==sum2;
    }
}

As you can see above, you can convert a character to its corresponding ASCII decimal number just by converting the character to an integer using casting.

Time and Memory Efficiency

The above code will have to iterate over each element to calculate the total sum of each sentence. Therefore this algorithm, like the previous ones, has a time complexity of O(n). However, although the three methods as similarly quick, this last example doesn’t use any data structure; therefore, it is using less memory.

Conclusion

To summarise, we have seen how to write an anagram program in java. We have seen three different ways: sorting the characters, counting character occurrences, and calculating the total sum of the character ASCII values. These three approaches are similarly fast with time complexity of O(n); however, the third approach is the best choice since it uses less memory.

I hope you enjoy the article, and thank you so much for reading and supporting this blog!

More Interesting Articles

Maven Jar Plugin – How to make an executable jar file

Install Hadoop on Mac – Ultimate Step by Step Guide

Runnable vs Callable – Find out the differences

How to Write a Tic Tac Toe Game in Java using classes