Java Collections (HashMap) - Anagram Check of Two Strings

 

Continuing our streak with String related Java Interview Questions, we'll try to solve one of popular Interview questions for Java - find if two Strings are Anagrams. We'll be utilizing the Java Collections framework to solve this problem. 

So, lets' begin!

If you've not already checked Anagram definition from Wikipedia, Anagram is a Word or Phrase which is formed by re-arranging the letters of another word. 

eg. GAINLY and LAYING are Anagrams, and so are FRIED and FIRED.

So, if two Strings are Anagrams, the core concept is that, the letters that these Strings contain will be exactly the same, and will occur the same number of times!

In order to solve this problem, we'll basically have to find out the unique letters that are occurring in a String, and on top of that, we'll have to find the number of occurrences of these letters. 

Java Collections has a perfect answer to solve this problem -> Hashmaps

We'll break down this problem into two parts. First we'll write a function to load a String into a Hashmap. And then we'll reuse this function for the Two strings, and compare the loaded Hashmaps. 

Let's first start with the function to load a String into a Hashmap. 

We need to import the Hashmap class from java.util.

import java.util.HashMap;

We'll try to cover another test case, to remove any whitespaces in the String so that whole sentences can be compared. 

System.out.println("Input String: " + input);

input = input.toLowerCase().replace(" ", "");

System.out.println("Processed String: " + input);

You can upgrade the code to clean out other characters as well. 

Now we'll declare a Hashmap.

HashMap<Character, Integer> hm = new HashMap<Character, Integer>();

We'll use the Characters of the String as Keys and the Occurrences as Values. Keys are unique in a Hashmap, and the Values can be changed as per the number of occurrences. 

Now, we will start scanning the characters of the String one by one, and load into the Hashmap. If a Character is already there (key), then we'll read the value of the Key and increment the value by one. 

for (int i = 0; i < input.length(); i++)

Now checking if key is present in Hashmap, and increment the count of value by 1. We'll then replace the original (key, value) pair

if (hm.containsKey(input.charAt(i))) {
    Integer count = hm.get(input.charAt(i));
    hm.replace(input.charAt(i), count + 1);
}

If not present, then simply load it into the hashmap.

else {
	hm.put(input.charAt(i), 1);
}

Cool, the logic is now written, we just need to return the generated Hashmap now!

Here's the reusable function for your reference. 

/**
 * Load a String Characters into a Hashmap
 * 
 * @author computengine.com
 * @param input
 * @return
 */

public HashMap<Character, Integer> loadStringToHashmap(String input) {

	System.out.println("Input String: " + input);

	input = input.toLowerCase().replace(" ", "");

	System.out.println("Processed String: " + input);

	HashMap<Character, Integer> hm = new HashMap<Character, Integer>();

	for (int i = 0; i < input.length(); i++) {
		if (hm.containsKey(input.charAt(i))) {
			Integer count = hm.get(input.charAt(i));
			hm.replace(input.charAt(i), count + 1);
		} else {
			hm.put(input.charAt(i), 1);
		}
	}

	System.out.println("HashMap generated: " + hm.toString());

	return hm;

}

Now comes the next part. We'll reuse the above function for a pair of strings and check if they are anagrams. This logic can now be used to compare n number of Strings!

We'll write a separate function to check this now. We'll declare two Hashmaps and call the above functions to load the Strings into them.

HashMap<Character, Integer> hm1 = loadStringToHashmap(a);
HashMap<Character, Integer> hm2 = loadStringToHashmap(b);

Now we simply have to compare the two Hashmaps. We can do that using the inbuilt function. 

if (hm1.equals(hm2))
    return true;
else
    return false;

Here's the function for your reference. 

/**
 * Check if String is an Anagram
 * 
 * @author computengine.com
 * @param a
 * @param b
 * @return
 */
public boolean checkAnagram(String a, String b) {

	HashMap<Character, Integer> hm1 = loadStringToHashmap(a);
	HashMap<Character, Integer> hm2 = loadStringToHashmap(b);

	if (hm1.equals(hm2))
		return true;
	else
		return false;
}

Now to check the output. 

StringAnagram sa = new StringAnagram();

System.out.println("Strings are Anagrams:"+sa.checkAnagram("fired gainly","fried laying"));

Generated output: 

Input String: fired gainly

Processed String: firedgainly

HashMap generated: {a=1, r=1, d=1, e=1, f=1, g=1, i=2, y=1, l=1, n=1}

Input String: fried laying

Processed String: friedlaying

HashMap generated: {a=1, r=1, d=1, e=1, f=1, g=1, i=2, y=1, l=1, n=1}

Strings are Anagrams:true

Thanks for Reading the Article. If you have reached this far, we hope that the article was useful to you! Please Like/Share/Follow us on Facebook, Twitter, Tumblr.