Thursday, 21 April 2016

Check if given strings are anagram or not - Java program

Write a Java program to find whether the given strings are anagrams or not is a frequently asked Java interview question. Some other frequently asked Java programs are counting chars in a string and given string is a palindrome or not. First thing here is to know what exactly is Anagram.

What is anagram

Two strings are called anagram if you can rearrange the letters of one string to produce the second string, using all the letters of the first string only once. While doing that, usually, you don't consider spaces and punctuation marks.

Some Examples - "keep" and "peek", "School Master" and "The Classroom".

Logic

To check whether the given strings are anagrams or not can be done by -
  • sorting both the strings
  • or
  • by iterating one of the string char by char and making sure that the second string has the same character present

Sorting logic

Since both strings should have the same set of characters so sorting them will make them similar strings.
So the steps are -

  1. Convert the passed strings to lower case and remove spaces.
  2. Check if both strings are of same length.
  3. Sort both Strings.
  4. Check if strings are similar using equals() method.

Iteration logic

You can iterate one of the String character by character and make sure that another string also has that character present. Here one thing is important if char is found in second string you need to delete that character from the second string.

Not doing that will mean - If first string has some specific character more than once and in second string that character is present only once, that same character will match every time.

So the steps are -

  1. Convert the passed strings to lower case and remove spaces.
  2. Check if both strings are of same length.
  3. Convert one string to char array and iterate through that array.
  4. Look for that character in the second string.
  5. If found delete it from the second string. Note that in StringBuilder class there is a method deleteCharAt() which is used for deleting the char. If you want to use String class in place of StringBuilder then in order to delete the char you'll have to write -

    String2.substring(0, index) + String2.substring(index+1);

Java Program

import java.util.Arrays;

public class Anagram {

 public static void main(String[] args) {
  // Using Sorting logic
  areAnagramsBySorting("School Master", "The classroom");
  areAnagramsBySorting("Keep", "Peek");
  areAnagramsBySorting("Keep", "Peel");
  
  // using iteration and deletion
  areAnagramsByIteration("Abc", "ca B");
  areAnagramsByIteration("Keep", "pEek"); 
  areAnagramsByIteration("Mary", "Army");
  areAnagramsByIteration("Mary", "Aermy");

 }
 
 /**
  * To find out if two strings are anagram using sort logic 
  * @param string1
  * @param string2
  */
 public static void areAnagramsBySorting(String string1, String string2) {
  //convert String to all lower cases and remove spaces
  String temp1 = prepString(string1);
  String temp2 = prepString(string2);
  
  boolean flag = true;
  // check for length
  if(temp1.length() != temp2.length()){
   flag = false;
  }
  // sort the strings
  temp1 = sort(temp1);
  temp2 = sort(temp2);
  
  flag =  temp1.equals(temp2);
  if(flag){
   System.out.println(string1 + " and " + string2 + " are anagrams");
  }else{
   System.out.println(string1 + " and " + string2 + " are not anagrams");
  }
 }
 
 /**
  * To find out if two strings are anagram using iteration and deletion logic 
  * @param string1
  * @param string2
  */
 public static void areAnagramsByIteration(String string1, String string2) {
  //convert String to all lower cases and remove spaces
  String temp1 = prepString(string1);
  String temp2 = prepString(string2);
  
  boolean flag = true;
  int index;
  // check for length
  if(temp1.length() != temp2.length()){
   flag = false;
  }
  
  char[] strArray = temp1.toCharArray();
  StringBuilder sb = new StringBuilder(temp2);
  
  for(char c : strArray){
   // Look for the char in second String
   index = sb.indexOf(""+c);
   // If found delete it, otherwise second occurrence of the
   // similar char in first string will be found in second String
   if(index != -1){
    sb.deleteCharAt(index);
   }else{ 
    flag = false;
    break;
   }    
  }
  if(flag){
   System.out.println(string1 + " and " + string2 + " are anagrams");
  }else{
   System.out.println(string1 + " and " + string2 + " are not anagrams");
  }
  
 }
 
 // Sort the given String 
 protected static String sort(String string) {
     char[] charArray = string.toCharArray();
     Arrays.sort(charArray);
            return new String(charArray);
    }
 
 // Method to convert String to all lower cases and remove spaces
 protected static String prepString(String string) {
    
            return string.toLowerCase().replaceAll("\\s", "");
    } 
}

Output

School Master and The classroom are anagrams
Keep and Peek are anagrams
Keep and Peel are not anagrams
Abc and ca B are anagrams
Keep and pEek are anagrams
Mary and Army are anagrams
Mary and Aermy are not anagrams

So these are the ways to find if given strings are anagram or not. Please let me know if you have any other logic to do that.


Related Topics

  1. How to Sort elements in different order in TreeSet
  2. Count total number of times each character appears in a String
  3. How to sort arraylist of custom objects in Java
  4. Print odd-even numbers using threads and semaphore
  5. Count number of words in a String

You may also like -

>>>Go to Java Programs page

No comments:

Post a Comment