What is an Anagram?
An anagram is a word which is formed by rearranging or shuffling of letters in another word, the most important property in Anagram is that all the letters have to be used only once. For example, let’s take the popular anagram, LISTEN is an anagram of SILENT. In this Anagram Program in Java, we will look into some the possible ways to check if two Strings are Anagram or Not.
Java Anagram Program
Method 1: Check if Two Strings Are Anagram using Array
This is the simplest of all methods. After getting the strings from the user and we need to first remove all the white space and convert them into the lower case for a non-case sensitive comparison. Now convert them into a character array and sort them alphabetically. Just compare both arrays has the same elements.
package com.javainterviewpoint;
import java.util.Arrays;
import java.util.Scanner;
public class AnagramChecker
{
public static void main(String[] args)
{
Scanner scanner = new Scanner(System.in);
// Getting the input string from the user
System.out.print("Enter the First String : ");
String s1 = scanner.nextLine();
System.out.print("Enter the second String : ");
String s2 = scanner.nextLine();
if(checkAnagram(s1, s2))
System.out.println(s1+" and "+s2+" are Anagrams");
else
System.out.println(s1+" and "+s2+" are NOT Anagrams");
scanner.close();
}
public static boolean checkAnagram(String s1, String s2)
{
// Remove all the white space
s1 = s1.replaceAll("\\s", "");
s2 = s2.replaceAll("\\s", "");
// Check if both length matches
if(s1.length() != s2.length())
return false;
else
{
// Convert both Strings into lower case and into Character Array
char[] arr1 = s1.toLowerCase().toCharArray();
char[] arr2 = s2.toLowerCase().toCharArray();
// Sort both Character Array
Arrays.sort(arr1);
Arrays.sort(arr2);
// Check if both arrays are equal
return (Arrays.equals(arr1, arr2));
}
}
}
- Get the input Strings from the user and read it using Scanner
String s1 = scanner.nextLine();
String s2 = scanner.nextLine();
- Remove all the white space from both the Strings s1 and s2, by passing the string to the replaceAll() method. We are using using regex “\\s” [\\s is regex for whitespace] and replacing it with “”
s1 = s1.replaceAll(“\\s”, “”);
s2 = s2.replaceAll(“\\s”, “”);
- Validate the length of both Strings if they match proceed further as it is the most important property all the letters have to be used at least once.
- Now convert strings s1 and s2 into lowercase by calling toLowerCase() and into a character Array using toCharArray() method
char[] arr1 = s1.toLowerCase().toCharArray();
char[] arr2 = s2.toLowerCase().toCharArray();
- Sort both the arrays arr1 and arr2 in ascending order using Arrays.sort() method
- Validate whether both arrays arr1 and arr2 are equal using Arrays.equal() method, this method returns true if both the arrays contains the same elements in the same order.
Arrays.equals(arr1, arr2)
- Finally, print the output based on the boolean returned from the checkAnagram() method.
Output:
Enter the First String : Listen Enter the second String : Silent Listen and Silent are Anagrams
Method 2: Anagram Program in Java without using Array
This is the primitive method to check if two Strings are Anagram, where we will be iterating each character of the first string and removing the particular character from the second string when found. If there are no characters left in the second string then both the strings are an anagram.
package com.javainterviewpoint;
import java.util.Scanner;
public class AnagramChecker
{
public static void main(String[] args)
{
Scanner scanner = new Scanner(System.in);
// Getting the input string from the user
System.out.print("Enter the First String : ");
String s1 = scanner.nextLine();
System.out.print("Enter the second String : ");
String s2 = scanner.nextLine();
if (checkAnagram(s1, s2))
System.out.println(s1 + " and " + s2 + " are Anagrams");
else
System.out.println(s1 + " and " + s2 + " are NOT Anagrams");
scanner.close();
}
public static boolean checkAnagram(String s1, String s2)
{
// Remove all the white space and convert to lower case
s1 = s1.replaceAll("\\s", "").toLowerCase();
s2 = s2.replaceAll("\\s", "").toLowerCase();
// Check length of both strings
if (s1.length() != s2.length())
return false;
else
{
for (int i = 0; i < s1.length(); i++)
{
for (int j = 0; j < s2.length(); j++)
{
if (s1.charAt(i) == s2.charAt(j))
{
s2 = s2.substring(0, j) + s2.substring(j + 1);
break;
}
}
}
if (s2.length() == 0)
{
return true;
} else
{
return false;
}
}
}
}
- Get the input Strings from the user and read it using Scanner
String s1 = scanner.nextLine();
String s2 = scanner.nextLine();
- Now remove all the white space from both the Strings s1 and s2, by passing the string to the replaceAll() method and convert them into lower case by calling the toLowerCase()
s1 = s1.replaceAll(“\\s”, “”).toLowerCase();
s2 = s2.replaceAll(“\\s”, “”).toLowerCase();
- Iterate each character of the String s1 with String s2, if a match is found then remove the particular character from s2 using substring() method
- If both Strings are anagram then String s2 should be left with no characters, if not then String s1 and s2 are not anagrams.
Method 3: Anagram Program
In this approach, we will be incrementing the counter of each character in the first array and decrementing the counter for each character in the second array. So if both the strings are an anagram, then the count gets tallied and the array will be filled with zeros.
package com.javainterviewpoint;
import java.util.Scanner;
public class AnagramChecker
{
public static void main(String[] args)
{
Scanner scanner = new Scanner(System.in);
// Getting the input string from the user
System.out.print("Enter the First String : ");
String s1 = scanner.nextLine();
System.out.print("Enter the second String : ");
String s2 = scanner.nextLine();
if (checkAnagram(s1, s2))
System.out.println(s1 + " and " + s2 + " are Anagrams");
else
System.out.println(s1 + " and " + s2 + " are NOT Anagrams");
scanner.close();
}
public static boolean checkAnagram(String s1, String s2)
{
// Remove all the white space, convert to lower case & character array
char[] arr1 = s1.replaceAll("\\s", "").toLowerCase().toCharArray();
char[] arr2 = s2.replaceAll("\\s", "").toLowerCase().toCharArray();
if (arr1.length != arr2.length)
return false;
// int array to hold value for 26 alphabets
int[] value = new int[26];
for (int i = 0; i < arr1.length; i++)
{
// Increment the value at index i by 1
value[arr1[i] - 97]++;
// Decrement the value at index i by 1
value[arr2[i] - 97]--;
}
// Value array will have only zeros, if strings are anagram
for (int i = 0; i < 26; i++)
if (value[i] != 0)
return false;
return true;
}
}
- Read the input from the user and replace all the white space from both the Strings s1 and s2, bypassing the string to the replaceAll() method, convert them into the lower case by calling the toLowerCase() method and finally convert them into character array using toCharArray() method
char[] arr1 = s1.replaceAll(“\\s”, “”).toLowerCase().toCharArray();
char[] arr2 = s2.replaceAll(“\\s”, “”).toLowerCase().toCharArray();
- Create an int array, to hold the count for each character, we set the array size as 26 [as we have 26 alphabets].
int[] value = new int[26];
- Now Increment the value array at index i by 1 for arr1 and Decrement the value array at index i by 1 for arr2, and finally check the content of value array and it should be zero’s if both strings are anagram.
value[arr1[i] – 97]++;
value[arr2[i] – 97]–;
Let’s understand the logic behind this a little deeper, assume the value of String s1 is “abc” and String s2 is “cba”
Since the value is an integer array, will have all the positions filled with zero during initialization
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
Loop 1:
arr1[i] will be ‘a’ and we are subtracting it with 97 because the ASCII of lower case alphabets start at 97.We will be actually doing [(ASCII of a) – 97]++ which will be value[0]++
Now value array will look like [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
arr2[i] is ‘c’, after subtracting with 97, we will get value[2]- –
value array will be like this [1, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
Loop 2:
arr1[i] –> ‘b’ and b – 97 will be 1 as ASCII of b is 98, so we will incrementing value[1] by 1 which will bevalue[1]++
Now value array will looks like[1, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
arr2[i] is also ‘b’, now we will be decrementing value[1] by 1 which will be value[1]- –
value –>[1, 0,-1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
Loop 3:
arr1[i] is ‘c’ after subtraction(99-97) we will get value[2]++
value –>[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
arr2[i] is ‘a’ after subtraction(97-97) we will get value[0]- –
value –>[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
So at the end of the iteration we can see that all the values of the value array is full of zeros.
Method 4: Anagram Program using XOR
Bitwise XOR returns the bit by bit XOR of the digits, if the bits are different it returns 1 and if bits are same it returns 0.
package com.javainterviewpoint;
import java.util.Scanner;
public class AnagramChecker
{
public static void main(String[] args)
{
Scanner scanner = new Scanner(System.in);
// Getting the input string from the user
System.out.print("Enter the First String : ");
String s1 = scanner.nextLine();
System.out.print("Enter the second String : ");
String s2 = scanner.nextLine();
if (checkAnagram(s1, s2))
System.out.println(s1 + " and " + s2 + " are Anagrams");
else
System.out.println(s1 + " and " + s2 + " are NOT Anagrams");
scanner.close();
}
public static boolean checkAnagram(String s1, String s2)
{
// Remove all the white space, convert to lower case & character array
char[] arr1 = s1.replaceAll("\\s", "").toLowerCase().toCharArray();
char[] arr2 = s2.replaceAll("\\s", "").toLowerCase().toCharArray();
if (arr1.length != arr2.length)
return false;
int xor = 0;
for (int i = 0; i < arr1.length; i++)
{
xor ^= arr1[i] ^ arr2[i];
}
return xor == 0? true: false;
}
}
We know Bitwise XOR returns 1 if the digits are different and 0 if the digits are same. After all the XOR’ing process if the result is 0 then the strings are anagrams.
Let’s now understand what happens behind the scene.
Again let’s assume the value of String s1 as “abc” and String s2 as “cba”. We have a local variable xor which is initialized to ‘0’ and the process continues like this, we will be XOR’ing xor and arr1[] and the result is again XOR’ed with arr2[] and stored in xor variable and the loop continues till the length of the array.
When i =0
- At first, the value of xor is ‘0’, we will XOR’ing it will arr1[i] which is ‘a’, the ASCII of a is 97.
- XOR’ing 0 and 97 will give a binary result of 1100001
- Now 1100001 will be XOR’ed with arr2[i], which will be ‘c’ (the ASCII of c is 99)
- XOR’ing 1100001 and 99 will return “10” (binary), it will be stored in the xor variable.
When i=1
- Now the value of xor is “10”, arr1[1] will is ‘b’ (ASCII of b is 98)
- XOR of 10 and 97 will be 1100000 (binary)
- Again XOR of 1100000 and 98 (arr2[1] is also ‘b’), will be again “10”(binary) which gets stored in the xor variable.
When i=2
- Value of xor is “10” and arr1[2] is ‘c’ and its ASCII value is 99
- XOR’ing 10 and 99 will return a binary of 1100001
- Now XOR 1100001 with 97 since arr2[2] is ‘a’ and the result will be 0
So whenever the resultant value is “0” then the two string are anagrams
Method 5: Check Anagram using HashMap
package com.javainterviewpoint;
import java.util.HashMap;
import java.util.Scanner;
public class AnagramChecker
{
public static void main(String[] args)
{
Scanner scanner = new Scanner(System.in);
// Getting the input string from the user
System.out.print("Enter the First String : ");
String s1 = scanner.nextLine();
System.out.print("Enter the second String : ");
String s2 = scanner.nextLine();
if (checkAnagram(s1, s2))
System.out.println(s1 + " and " + s2 + " are Anagrams");
else
System.out.println(s1 + " and " + s2 + " are NOT Anagrams");
scanner.close();
}
public static boolean checkAnagram(String s1, String s2)
{
if (s1.length() != s2.length())
return false;
HashMap<Character, Integer> map = new HashMap<Character, Integer>();
for (int i = 0; i < s1.length(); i++)
{
char c = s1.charAt(i);
if (map.containsKey(c))
map.put(c, map.get(c) + 1);
else
map.put(c, 1);
}
for (int i = 0; i < s2.length(); i++)
{
char c = s2.charAt(i);
if (map.containsKey(c))
{
if (map.get(c) == 1)
map.remove(c);
else
map.put(c, map.get(c) - 1);
} else
return false;
}
if (map.size() > 0)
return false;
return true;
}
}
- In this approach, we will be incrementing the value of the key for the first array and decrement the value for the second array and finally validate the map size.
- After the conversion of the Strings into a character array, we will be iterating through the values of arr1, if the hashmap already has the particular key then increment its value by 1.
if (map.containsKey(c))
map.put(c, map.get(c) + 1);
- If the particular key is not present then using the put() add the character to hashmap and set its value to 1.
map.put(c, 1);
- For the second array arr2, we will be doing the reverse of what we did for arr1 if the hashmap already has the particular key and if the value is 1, then remove the particular entry from the map
if (map.get(c) == 1)
map.remove(c);
- If the value of the particular character is greater than 1, then decrement the value of that particular key by 1.
map.put(c, map.get(c) – 1);
- Finally, validate the size of the map, if it is greater than zero then return false which means the strings are not anagrams, if the size is zero then the two strings are anagrams.
if (map.size() > 0)
return false;
Method 6: Anagram Program in Java Using ArrayList
This approach is almost similar to Method 1, where instead of using array we will be using a list. We will be adding each character of the strings into the list and check if both the lists are equal.
package com.javainterviewpoint;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;
public class AnagramChecker
{
public static void main(String[] args)
{
Scanner scanner = new Scanner(System.in);
// Getting the input string from the user
System.out.print("Enter the First String : ");
String s1 = scanner.nextLine();
System.out.print("Enter the second String : ");
String s2 = scanner.nextLine();
if (checkAnagram(s1, s2))
System.out.println(s1 + " and " + s2 + " are Anagrams");
else
System.out.println(s1 + " and " + s2 + " are NOT Anagrams");
scanner.close();
}
public static boolean checkAnagram(String s1, String s2)
{
s1 = s1.replaceAll("\\s", "").toLowerCase();
s2 = s2.replaceAll("\\s", "").toLowerCase();
if (s1.length() != s2.length())
return false;
List<Character> list1 = new ArrayList<Character>();
List<Character> list2 = new ArrayList<Character>();
for (int i = 0; i < s1.length(); i++)
{
list1.add(s1.charAt(i));
}
for (int i = 0; i < s2.length(); i++)
{
list2.add(s2.charAt(i));
}
Collections.sort(list1);
Collections.sort(list2);
if (list1.equals(list2))
return true;
else
return false;
}
}
Happy Learning !! 🙂 Do let me know if you come across any new way to Check if Two Strings are Anagram or Not?
Leave a Reply