Friday, November 20, 2015

Anagram String and its solutions

Hello Friends, today I want to discuss something about the anagram strings.

Now What is an Anagram String?
   "An anagram is a type of word play, 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, the word anagram can be rearranged into nag-a-ram." - Wiki

Now if I understood correctly then in one way or the other we have to use the same letters that are there in first word for exactly the same number of times they appeared in it, for the second word in any order.

Now coming to the solution part. There are many ways of checking the anagram strings.
  1. Using the sorting solution
  2. Using the prime number solution
Using the Sorting Algorithm:
    This is pretty simple way of checking the Anagram Strings. In this we sort both the Strings that we get for being checked as Anagram and then checks that both the results should be identical.

  For example: 
    If I pass 2 strings, say Anagram and Nagaram, then the algo goes like this:
  • Checks whether the length of both the strings are same, if not there is no profit in going forward
  • Then change strings to lower case/Upper case, to make sure there should not be any difference because of the cases.
  • Sorts both the strings in their natural way either increasing or decreasing order
  • Then checks whether both the sorted results are identical
  Program:

public class AnagramCheck_Sort{
 public static boolean isAnagram(String s1, String s2){
  // Early termination check, if strings are of unequal lengths,
  // then they cannot be anagrams
  if (s1==null || s2==null || s1.length() != s2.length() ) {
   return false;
  }

  char[] c1 = s1.toLowerCase().toCharArray();
  char[] c2 = s2.toLowerCase().toCharArray();
  Arrays.sort(c1);
  Arrays.sort(c2);
  String sc1 = new String(c1);
  String sc2 = new String(c2);
  return sc1.equals(sc2);
 }
 public static void main(String[] args){
  System.out.println(isAnagram("Anagram","nagaram"));
 }
}

Using the prime number solution:
    This method is like the brute force. Here goes ihe algo:

  • Checks whether the length of both the strings are same if not there is no profit in going forward.
  • Then makes a map of character and assign 1 unique prime number to it.For instance assign character 'a' the prime number 2, and character 'b' the prime number 3 and so on for all 26 letters.
  • then runs the loop and keep on multiplying by the number that each character posses and keep it in a different variable as a product
  • At last because all the number were prime in nature and also the product of two unique primes are always unique we end up getting two products which tells us whether the strings are prime or not. If the two products are same then the strings are prime otherwise not
  • One point to note that because we are multiplying the numbers the variable should be of big datatype.
Program:
Here is running version : link

class AnagramCheck_Sort{
 public static boolean isAnagram(String s1, String s2){
  // Early termination check, if strings are of unequal lengths,
  // then they cannot be anagrams
  if (s1==null || s2==null || s1.length() != s2.length() ) {
   return false;
  }
  s1=s1.toLowerCase();s2=s2.toLowerCase();
  Integer p1 = 1; Integer p2 = 1;
  for(int i=0, len=s1.length(); i!=len; i++){
   char c1 = s1.charAt(i);char c2 = s2.charAt(i);
   p1 = p1 * primesMap.get(c1);p2 = p2 * primesMap.get(c2);
  }

  return p1.equals(p2);
 }
 public static void main(String[] args){
  primesMap.put('a',2);primesMap.put('b',3);primesMap.put('c',5);primesMap.put('d',7);primesMap.put('e',11);primesMap.put('f',13);
  primesMap.put('g',17);primesMap.put('h',19);primesMap.put('i',23);primesMap.put('j',29);primesMap.put('k',31);primesMap.put('l',37);
  primesMap.put('m',41);primesMap.put('n',43);primesMap.put('o',47);primesMap.put('p',53);primesMap.put('q',59);primesMap.put('r',61);
  primesMap.put('s',67);primesMap.put('t',71);primesMap.put('u',73);primesMap.put('v',79);primesMap.put('w',83);primesMap.put('x',89);
  primesMap.put('y',97);primesMap.put('z',101);
 
  System.out.println(isAnagram("Anagram","nagaram"));
 }
 
 private static Map<character ,Integer> primesMap = new HashMap<>();
}

No comments:

Post a Comment