In this article, we will see different Java algorithms to determine if two Strings are anagrams of each other.
These programs can be used to check if a String is a permutation of another String.
 

What is an Anagram ?

Two String or words are said to be Anagrams of each other if they share the same set of letters to form the respective words.
 
For example,

Silent–>Listen,
post–>opts

In case of phrases, you can compare them irrespective of the spaces.
For example,

Dormitory -> dirty room
Tom Marvolo Riddle -> I am Lord Voldemort

 

Anagram Program 1 : Using sorting

In this approach, we remove the spaces from the Strings, convert them lowercase and then sort them. If the Strings are anagrams, both will have same characters at same positions after sorting and can be compared using Arrays.equals or using a loop.

package com.topjavatutorial;

import java.util.Arrays;
import java.util.Scanner;

public class AnagramProgram {

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    System.out.println("Enter first string");
    String str1 = sc.nextLine();
    System.out.println("Enter second string");
    String str2 = sc.nextLine();
    System.out.println("Checking for anagram returned " + isAnagram(str1,str2));
  }
  
  public static boolean isAnagram(String str1, String str2){
    char[] charArr1 = str1.replaceAll("[\\s]", "").toLowerCase().toCharArray();
    char[] charArr2 = str2.replaceAll("[\\s]", "").toLowerCase().toCharArray();
    
    Arrays.sort(charArr1);
    Arrays.sort(charArr2);
    
    return(Arrays.equals(charArr1, charArr2));
  }

}

 
 

Output

 
Enter first string
 
Dave Barry
 
Enter second string
 
Ray Adverb
 
Checking for anagram returned true

 

Anagram Program 2 : Using HashMap

We can use a HashMap to store the characters as keys and respective counts as values. Now, while iterating first array, we set each count to 1 or increment for duplicates. Simialrly, while going through the second array, we decrement the count. At the end of both loops, the count for each character should be zero if the Strings are anagrams.

  private static boolean isAnagram(String str1, String str2) {
    if (str1.length() != str2.length())
      return false;
    char[] charArr1 = str1.replaceAll("[\\s]", "").toLowerCase().toCharArray();
    char[] charArr2 = str2.replaceAll("[\\s]", "").toLowerCase().toCharArray();
    Map<Character, Integer> map = new HashMap<Character, Integer>();

    for (char ch : charArr1) {
      int n = 1;
      if (map.containsKey(ch))
        n++;
      map.put(ch, n);
    }

    System.out.println(map);

    for (char ch : charArr2) {
      int n = 1;
      if (map.containsKey(ch))
        n--;
      map.put(ch, n);
    }
    System.out.println(map);

    for (char ch : map.keySet()) {
      if (map.get(ch) != 0)
        return false;
    }
    return true;
  }

 

Anagram Program 3 : Using for loop with StringBuilder

In this approach, we loop through one array while comparing and removing from the second until we find a mismatch or all the characters are covered.

  private static boolean isAnagram(String str1, String str2) {
    if (str1.length() != str2.length())
      return false;
    StringBuilder sb = new StringBuilder(str2);
    int index;
    for (char ch : str1.toCharArray()) {
      index = sb.indexOf(String.valueOf(ch));
      if (index == -1)
        return false;
      else {
        sb.deleteCharAt(index);
      }
      System.out.println(sb.toString());
    }
    
    return true;
  }

 

Anagram Program 4 : Using a separate array for counts

In this approach, we create a separate int array for count. We increment the count of each character for first array and similarly decrement count of each character for second array.
If the Strings are anagrams, the array should only have zeroes in it.

  private static boolean isAnagram4(String str1, String str2){
    if (str1.length() != str2.length())
      return false;
    char[] charArr1 = str1.replaceAll("[\\s]", "").toLowerCase().toCharArray();
    char[] charArr2 = str2.replaceAll("[\\s]", "").toLowerCase().toCharArray();
    
        int[] counts = new int[26]; 
        for (int i = 0; i < charArr1.length; i++){
            counts[charArr1[i]-97]++;  // Increment the count of the character at i
            counts[charArr2[i]-97]--;  // Decrement the count of the character at i
        }
        // If the strings are anagrams, the counts array will be full of zeros
        for (int i = 0; i<26; i++)
            if (counts[i] != 0)
                return false;
        return true;
    }

 

© 2016 – 2018, https:. All rights reserved. On republishing this post, you must provide link to original post