Given a sequence of words, print all anagrams together in Java

May 18, 2022

Print all Anagrams Together

Today we will be learning how to print all anagram together using Java programming language.

  • Input : wordArr[] = { “cat”, “dog”, “tac”, “god”, “act”,”z” }
  • Output : cat tac act dog god z

here the output of the current input is cat tac act dog god z as it’s printing all anagrams together

print all anagrams together in Java

Algorithm

  • Creating a Hash Table is a simple method. Determine the hash value of each word so that all anagrams have the same hash value. Fill in the hash values in the Hash Table.
  • Finally, print those words with the same hash values together. The modulo sum of all characters can be used to implement a simple hashing mechanism. Two non-anagram words can have the same hash value when using modulo sum. Individual characters can be matched to handle this.
  • In the following program, an array of structure “Word” is used to store both index and word arrays. Dupray is another structure that stores an array of structure “Word”. 
Print All Anagrams Together

The idea is to sort each word on the list and construct a map where the map’s key is each sorted word, and the map’s value is a list of indices in the array where it is present. After creating the map, traverse the map and get indices for each sorted key. The anagrams are present in the actual list at those indices.

Print all Anagrams Together Java Code

Run
 import java.util.Arrays;
 import java.util.Comparator;
 public class Main { 
  // class for each word of duplicate array
  static class Word {
    String str; // to store word itself
    int index; // index of the word in the

    Word(String str, int index)
    {
      this.str = str;
      this.index = index;
    }
}

// class to represent duplicate array.
static class DupArray {
  Word[] array; // Array of words
  int size; // Size of array

// constructor
  public DupArray(String str[], int size)
  {
    this.size = size;
    array = new Word[size];

  int i;
  for (i = 0; i < size; ++i) {
  // create a word Object with the
  // str[i] as str and index as i
    array[i] = new Word(str[i], i);
    }
   }
 }


  static class compStr implements Comparator {
  public int compare(Word a, Word b)
  { 
    return a.str.compareTo(b.str);
  }
}

 // Given a list of words in wordArr[],
  static void printAnagramsTogether(String wordArr[],
  int size)
  {
  // Step 1: Create a copy of all words present
  // in given wordArr. The copy will also have
  // original indexes of words
  DupArray dupArray = new DupArray(wordArr, size);

  // Step 2: Iterate through all words in
  // dupArray and sort individual words.
  int i;
  for (i = 0; i < size; ++i) {
  char[] char_arr = dupArray.array[i].str.toCharArray();
  Arrays.sort(char_arr);
  dupArray.array[i].str = new String(char_arr);
 }

  // Step 3: Now sort the array of words in
  // dupArray
  Arrays.sort(dupArray.array, new compStr());

  for (i = 0; i < size; ++i)
  System.out.print(
  wordArr[dupArray.array[i].index] + " ");
}

// Driver program to test above functions
public static void main(String args[])
{
  String wordArr[] = { "cat", "dog", "tac", "god", "act" };
  int size = wordArr.length;
  printAnagramsTogether(wordArr, size);
 }
}

 

cat tac act dog god
Java Online Course Banner