Check If two strings are Anagrams.

Check 2 strings are anagrams of each other.


What is Anagram?

An anagram is a rearrangement of the letters of one word or phrase to another word or phrase, using all the original letters exactly once.

Example:
1. "evil" and "vile" is anagram of each other
2.
"dog" and "ogd" is anagram of each other
3. "burger" and "burgr" is not a anagram of each other

Algorithm


We will take a count array of length 26 because any word is made up from total 26 characters
(a, b, c ... z).

int[] counts = new int[26]; 


For character 'a' in a string, we will increment the count at counts[0],
For character 'b' in a string, we will increment the count at counts[1],  and so on.

How we will identify the count arrray index from character?

ASCII code of a = 97
ASCII code of b = 98
ASCII code of c = 99
.
.
.
ASCII code of z = 122

First character starts from 'a' having ASCII code 97, We will use this as base to identify index in count array.

Index for character 'a' will be calculated by (ASCII of 'a') - 97 = 97 - 97 = 0,

Index for character 'b' will be calculated by (ASCII of 'b') - 97 = 98 - 97 = 1, and so on.

Understanding Program


Iterate from 0 to string length,
Step 1. for each character in string1 increment the count at respective position in counts array.
Step 2. for each character in string2 decrement the count at respective position in counts array.

At the end, if count is 0 for all 26 positions in count array then characters are balanced in string 1 and string 2 and is ANAGRAM of each other otherwise not.


Another approach using HashMap.


Step 1. Create a Hashmap where key is character and value is count(number of times character occur).
Step 2. Iterate string 1, populate the hashmap and increment the count for repeated characters.
Step 3.
Iterate string 2, for each character, check character is present in map, if not, then stop as it
             not Anagram
. If character is present then decrement count.
            Also, remove element from hashmap if count is 0.
Step 4. At last, If hashmap is empty, then strings are anagram otherwise not.


Java Program to Check whether two strings are anagram of each other using Count array approach.


package javabypatel.miscellaneous;

/*
 * We increment the count of each character in the first array and 
 * decrement the count of each character in the second array. 
 * 
 * If the resulting counts array is full of zeros, then strings are anagrams otherwise not.
 */
public class Find2StringAreAnagramsOfEachOther {

 public static void main(String[] args) {
  String str1 = "abc";
  String str2 = "abc";
  System.out.println("Anagram?? :"+isAnagram(str1, str2));
 }

 private static boolean isAnagram(String a, String b){
  
  //if both string is null, then considering it as anagram.
  if(a==b){
   return true;
  }
 
  //if any one string is null, then they are not anagram.
  if(a==null || b==null)
   return false;
  
  //If length of both strings are not same then obviously they are not anagrams.
  if(a.length()!=b.length())
   return false;
  
  char[] aArr = a.toLowerCase().toCharArray(); 
  char[] bArr = b.toLowerCase().toCharArray();
  
  // An array to hold the number of occurrences of each character
  int[] counts = new int[26]; 
  
  for (int i = 0; i < aArr.length; i++){
   counts[aArr[i]-97]++;  // Increment the count of the character at respective position
   counts[bArr[i]-97]--;  // Decrement the count of the character at respective position
  }
  
  // If the strings are anagrams, then counts array will be full of zeros not otherwise
  for (int i = 0; i<26; i++){
   if (counts[i] != 0)
    return false;
  }
  
  return true;
 }
}


You may also like to see


Compress a given string in-place and with constant extra space.

Check whether a given string is an interleaving of String 1 and String 2.

Given two words (beginWord and endWord), and a dictionary's word list, find the length of shortest transformation sequence from beginWord to endWord.

Serialize and Deserialize a Binary Tree

Advanced Multithreading Interview Questions In Java

Given an array of integers. All numbers occur thrice except one number which occurs once. Find the number in O(n) time & constant extra space. 

Count number of Bits to be flipped to convert A to B 

Count number of Set Bits in Integer. 

Check if number is Power of Two. 

Find all subsets of a set (Power Set). 

Skyline Problem in Java. 

Find Minimum length Unsorted Subarray, Sorting which makes the complete array sorted 

Count trailing zeros in factorial of a number 

When to use SOAP over REST Web Service. Is REST better than SOAP? 

Tower Of Hanoi Program in Java. 


Enjoy !!!! 

If you find any issue in post or face any error while implementing, Please comment.

Post a Comment