Anagram Program in Java

Anagrams are those words that are generated by rearrangement of the letters of another phrase or word. Usually, while doing the rearrangement, the original letters are used only once. Anagrams are case-insensitive. Some examples of anagrams are:

Real fun = Funeral.

Elegant man = A Gentleman.

Voices rant on = Conversation.

Dirty room = Dormitory.

The classroom = School master.

The eyes = They see.

Silent = Listen.

Let’s observe the following program that illustrates how to check the two given strings are anagrams of each other or not.

Filename: AnagramStringExample.java

Output:

Explanation:

We have written the areAnagrams() method to find out the anagram strings. In the method, we remove the blank spaces as blank spaces do not take part in finding anagrams. After that, we check the length of the strings. If the string length-comparison results false, that means there are some extra characters is any one of the strings.

Hence, the given strings can never be anagrams, and we stop right there. If the comparison returns true, then we have to check the arrangements of letters. At this step, first, we deal with the case sensitivity of strings by changing each character of string into small-case then we do the sorting of character arrays so that every string has the same arrangement.

We changed the strings into character arrays because we do not have sorting methods in the Java String class. Finally, we make a comparison of character arrays and return the result.

Let us discuss one more approach, which is better than the above one in some cases.

Another Approach To Check Anagrams

Filename: AnagramStringExample1.java

Output:

Explanation: In this approach, we are using the technique of hashing to find the anagrams. In the previous approach, we used sorting to settle on the common arrangement for both the string. In this approach, we store the character as key and its frequency as the value in the two integer arrays, one array for each string. Finally, we compare values stores in the integers arrays to find the anagrams. At a particular index, if any value of the integer arrays differs, we are done.

Let us understand how to generate and store a key-value pair. Suppose we have a string “keen”. Then, the key-value pair will be:

KeyValue
k1
e2
n1

In an integer array, we will store arr[‘k’] = 1, arr[‘e’] = 2, arr[‘n’] = 1. Since the index of an array is always a whole number, therefore, ‘k’ internally gets converted to its ASCII value 107. ‘e’ gets 101 and ‘n’ gets 110. Thus, we have arr[107] = 1, arr[101] = 2, arr[110] = 1. Note that the size of a character in Java is 2 bytes. Therefore, the range of characters Java handles is 216 = 65536. Therefore, we have declared the size of integer arrays as 65536.

Comparison Between The Above Two Approaches

The major difference between the above two approaches is the first one relies on the sorting technique, while the latter one deals with hashing (storing key-value pair). The sorting approach does very well when the size of the string is small. However, the time consumption increases logarithmic times the size of the string when the size of the string increases. Therefore, for very large strings, the first approach takes a lot of time. 

In the second approach, storing key-value pairs is directly dependent on the size of the character array, which, in turn, is dependent on the size of the given string. Thus, for the larger strings, time consumption increases linearly, not logarithmically times the size of the string. Also, the loop that compares values runs 65536 times, which is irrespective of the size of the string. Thus, even for a string comprising of only 3-4 characters, the comparison-loop runs 65536 times, which is quite bad, but when we have a string containing millions or billions of characters, then 65536 times looks very good.

Conclusion: Hence, for the smaller strings, the first approach should be taken into consideration. The latter takes precedence when the string length is large.

Pin It on Pinterest

Share This