Sunday 20 September 2015

Find if two words are anagram or not

Problem


Given two words, find whether they are anagram or not. An anagram of a word is another word which can be obtained by rearranging the letters of the first word. Without any addition or deletion of letters.

Solution


We will use the property of anagrams that the count of different letters in anagrams are equal. So we will take one word and keep its letter's count in a hash map. Now for second word we will keep on decreasing the count form the map. When the count is zero, we will remove the key from the map. In this way if two words are anagram then nothing should be left in the map at the end of this operation. So we return true if the map has no keys left. If during removal we find that that some letter is not found for removal then also it is not an anagram. 


Code

import java.util.HashMap;
import java.util.Map;

public class OneWordPermutationOfOther
{
 public static void main(String[] args)
 {
  String a = "listen";
  String b = "enlist";
  System.out.println(isPermutation(a, b));
 }

 private static boolean isPermutation(String a, String b)
 {
  Map < Character, Integer> charMap = new HashMap < Character, Integer>();
  for (char ch : a.toCharArray())
  {
   if (charMap.containsKey(ch))
    charMap.put(ch, charMap.get(ch) + 1);
   else
    charMap.put(ch, 1);
  }
  for (char ch : b.toCharArray())
  {
   if (!charMap.containsKey(ch))
    return false;
   if (charMap.get(ch) == 1)
    charMap.remove(ch);
   else
    charMap.put(ch, charMap.get(ch) - 1);
  }
  if (charMap.keySet().size() == 0)
   return true;
  return false;
 }

}

No comments:

Post a Comment