Monday, July 28, 2014

Check if two Strings are Anagram in Java

This question was asked from me in a written test of a top IT MNC company. But, the way of asking the question was different. This question can be asked either directly or by giving an example.
This question can be solved by various methods but the interviewer always prefers the optimized one. But firstly, lets see what are anagram strings.

What are Anagram Strings

An anagram is a type of word, the result of rearranging the letters of a word or phrase to produce a new word or phrase, using all the original letters exactly once. For example: orchestra can be rearranged into carthorse or cat can be rearranged into act.

As I said, there are multiple ways to find if two string are anagram or not. The classical way is getting character array of each String, and then comparing them. If both char arrays are equal then Strings are anagram. But before comparing, make sure that both String are in same case i.e. either lowercase or uppercase and character arrays are sorted.

Now, lets see various solutions to solve this problem:

Solution 1 (Using Character Array)

In this appraoch, we get character array of each string and then compare both the arrays. If both arrays are equal then strings are anagram. Below is the implementation to check if two strings are anagrams using character array:
Below is the example of String functions:

public static boolean isAnagram(String str1, String str2) {
   if (str1.length() != str2.length()) {
      return false;
   }
   char[] chars = str1.toCharArray();
   for (char c : chars) {
      int index = str2.indexOf(c);
      if (index != -1) {
         str2 = str2.substring(0, index) + str2.substring(index + 1, str2.length());
      } else {
         return false;
      }
   }
   return str2.isEmpty();
}

Solution 2

In this approach, we'll use Arrays class of Java API. Below is the implementation of this approach:

public static boolean isAnagram(String str1, String str2) {
   char[] charOfStr1 = str1.toCharArray();
   char[] charOfStr2 = str2.toCharArray();
   Arrays.sort(charOfStr1);
   Arrays.sort(charOfStr2);
   return Arrays.equals(charOfStr1, charOfStr2);
}

Solution 3(Using StringBuilder)

Below is the implementation details of this approach:

public static boolean isAnagram(String first, String second) {
   char[] characters = first.toCharArray();
   StringBuilder sb = new StringBuilder(second);
   for (char ch : characters) {
      int index = sb.indexOf("" + ch);
      if (index != -1) {
         sb.deleteCharAt(index);
      } else {
         return false;
      }
   }
   return sb.length() == 0 ? true : false;
}

Solution 4 (Using Map)

Below is the implementation details of this approach:

public static boolean isAnagram(String str1, String str2) {
   if (str1 == null || str2 == null) {
     return false;
   } else if (str1.length() != str2.length()) {
      return false;
   }

   Map<Character, Integer> map = new HashMap<Character, Integer>();

   for (int i = 0; i < str1.length(); i++) {
     char characters = str1.charAt(i);
     int charInStr1 = map.containsKey(characters) ? map.get(characters) : 0;
     map.put(characters, ++charInStr1);
     char charFromStr2 = str2.charAt(i);
     int charsInRight = map.containsKey(charFromStr2) ? map.get(charFromStr2) : 0;
     map.put(charFromStr2, --charsInRight);
   }

   for (int occurrences : map.values()) {
     if (occurrences != 0) {
        return false;
     }
   }
   return true;
}