Given a set of random strings, write a function that returns a set that groups all the anagrams together.

Anagram is a form of word play in which letters of a word are rearranged in such a way that a new word is formed. Consider we have a word rats now by rearranging the characters if we can get another word then the word will be an anagram of rats. Consider the following examples of anagram set:

act, cat
tab, bat
tar, rat
star,rats

 

Algorithm to solve the problem:

We will use the following data structure to store the anagram set:   

Map<String, List<String>> anagramGroup = new HashMap<>();

Where the key is the sorted result of a word and the value is the list of all anagrams.

1. Iterate over the List/ Array of words.
   
   a.  For each word convert the word into character array. So if the word is "cat" then the array will be [c,a,t];
   b.  Sort the array, so here the resulting sorted array will be [a,c,t].
   c.  Again convert the array to String and check if there is any entry present for this key "act".
           i.  If entry is present then add the original word "cat" in the List present in value filed.
           ii. Else create a new List and add the original word "cat" in the list and place the list in value filed against the  sorted key.
    d. Now if the word "act"/"tac" comes. Then the sorted key will be "act". And we will find an entry for the key "act" and add both the
       word in the list.

Now let us check the Java implementation for the same

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Set;

/*	Given a set of random strings, write a function that returns 
 	a set that groups all the anagrams together.
 	Ex: star, dog, car, rats, ars - > {(star, rats), (src,car), dog)
 */

public class AnagramSet {

	public static void main(String[] args) {
		String[] StrArr = { "star", "dog", "car", "rats", "ars", "rca" };
		try {
			Map<String, List<String>> anagramGroup = getAnagramGroup(StrArr);
			print(anagramGroup);
		} catch (Exception e) {
			e.printStackTrace();
		}
	}

	private static Map<String, List<String>> getAnagramGroup(String[] StrArr)
			throws Exception {
		if (StrArr == null) {
			throw new Exception("Input String is null");
		}
		Map<String, List<String>> anagramGroup = new HashMap<>();
		List<String> anagrams = null;
		for (String s : StrArr) {
			char[] charArray = s.toCharArray();
			Arrays.sort(charArray);
			String sorted = String.copyValueOf(charArray);
			anagrams = anagramGroup.get(sorted);
			if (anagrams == null) {
				anagrams = new ArrayList<>();
				anagrams.add(s);
				anagramGroup.put(sorted, anagrams);
			} else {
				anagramGroup.get(sorted).add(s);
			}
		}
		return anagramGroup;
	}

	private static void print(Map<String, List<String>> anagramGroup) {
		Set<Entry<String, List<String>>> entrySet = anagramGroup.entrySet();
		for (Entry<String, List<String>> entry : entrySet) {
			if (entry.getValue() == null) {
				System.out.print("{" + entry.getKey() + "} ");
			} else {
				System.out.print("{");
				for (String s : entry.getValue()) {
					System.out.print(s + " ");
				}
				System.out.print("}");
			}
		}
	}
}

The output of the program is:

{car rca }{ars }{dog }{star rats }

 

core java 12 Algorithm 12

FOLLOW US ON LinkedIn



Explore Tutu'rself