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