Anagram Program in Java using String
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
public class AnagramStringExample
{
public static boolean areAnagrams(String a, String b)
{
//Removing blank spaces
String str1 = a.replaceAll("\\s", "");
String str2 = b.replaceAll("\\s", "");
//if lengths of strings are not equal, we are done.
if(str1.length() != str2.length())
return false;
//Handling the case-insensitivity scenario
char[] arrStr1 = str1.toLowerCase().toCharArray();
char[] arrStr2 = str2.toLowerCase().toCharArray();
// Sorting the character arrays.
Arrays.sort(arrStr1);
Arrays.sort(arrStr2);
return Arrays.equals(arrStr1, arrStr2); //Comparing strings and returning result
}
public static void main(String[] args)
{
String s1 = "Elegant Man", s2 = "A Gentleman";
if(areAnagrams(s1, s2))
System.out.println("The given strings are anagrams of each other.");
else
System.out.println("The given strings are not anagrams of each other.");
}
}
Output:
The given strings are anagrams of each other.
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
public class AnagramStringExample1
{
public static boolean areAnagrams(String a, String b)
{
//Removing blank spaces
String str1 = a.replaceAll("\\s", "");
String str2 = b.replaceAll("\\s", "");
//if lengths of strings are not equal, we are done.
if(str1.length() != str2.length())
return false;
//Handling the case-insensitivity scenario
char[] arrStr1 = str1.toLowerCase().toCharArray();
char[] arrStr2 = str2.toLowerCase().toCharArray();
int[] arr1 = new int[65536];
int[] arr2 = new int[65536];
//storing key-value pair
for(int i = 0; i < arrStr1.length; i++)
{
arr1[arrStr1[i]]++;
arr2[arrStr2[i]]++;
}
//comparing values of the integer arrays
for(int i = 0; i < 65536; i++)
{
if(arr1[i] != arr2[i])
return false;
}
return true;
}
public static void main(String[] args)
{
String s1 = "Elegant Man", s2 = "A Gentleman";
if(areAnagrams(s1, s2))
System.out.println("The given strings are anagrams of each other.");
else
System.out.println("The given strings are not anagrams of each other.");
}
}
Output:
The given strings are anagrams of each other.
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:
| Key | Value |
| k | 1 |
| e | 2 |
| n | 1 |
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.