CC-18 : Find anagrams with an array of Strings.

Description:

Two strings are anagrams if they are of the same length and contain the same characters. Given String input array arr, find and return Strings that are anagrams of at least one another String of the array. You can assume all the letters of input words are in lowercase.

Test cases and expected outputs:

Input Parameters	Expected outputs
strArray1 = {"listen", "near", "swim", "morning", "silent"};	Words that are Anagrams in the array: silent, listen
strArray1 = {"pins", "road", "ate", "eat", "tree", "spin", "tree"};	Words that are Anagrams in the array: ate, spin, tree, eat, pins
strArray1 = {"join", "roar", "smile", "art", "more", "dear", "pen"};	There are no words that are anagrams of any other String in the array.

Pseudocode:

The java method should accept following input parameters: arr (String array).

Initialize a variable wordsHash of type HashSet to hold the input elements.

Initialize a variable sortedCharHash of type HashSet. We will sort the characters of each element in arr and then save this sorted characters element in sortedCharHash. This will help us to find anagrams.

Initialize a variable anagrams of type HashSet to hold the anagrams we have found.

Using a for loop iterate through arr, using idx as a loop variable with initial value 0 and increment idx till it reaches arr1.length-1:

Call method sortedChars(arr[idx] and set the return value to SortedCharsStr.

If wordsHash does not contain sortedCharsStr, then we have not yet identified an anagram for sortedCharStr :

Add sortedCharStr to wordsHash.

If wordsHash contains sortedCharsStr, then we have identified an anagram for sortedCharStr:

Add sortedCharStr to sortedCharsAnagrams.

Using a for loop iterate through arr, using idx as a loop variable with initial value 0 and increment idx till it reaches arr1.length-1:

Call method sortedChars(arr[idx] and set the return value to SortedCharsStr.

If SortedCharsAnagrams contains sortedCharsStr, then we have identified that arr[idx] has anagrams in arr:

Add arr[idx] to anagrams.

After the loop completes the anagram elements of arr have added to anagrams.

Initialize a String array retval with size same as anagrams.size().

Use an iterator to access elements from anagrams and add the same to String array retVal. Return retVal.

The java method should accept following input parameters: str (String).

Initialize a char array chars of with characters from str using String.toCharArray() method.

Use Arrays.sort() method to sort chars.

Create a new String from chars and return it.

Code:

public String[] setFindAnagrams(String[] arr) {
	HashSet<String> wordsHash=new HashSet<String>();
	HashSet<String> sortedCharAnagrams=new HashSet<String>();
	HashSet<String> anagrams=new HashSet<String>();
	for (int idx=0; idx< arr.length; idx++) {
		String sortedCharsStr=sortedChars(arr[idx]);
		if (! wordsHash.contains(sortedCharsStr)) {
			wordsHash.add(sortedCharsStr);
		}else {
			sortedCharAnagrams.add(sortedCharsStr);
		}
	}
	for (int idx=0; idx< arr.length; idx++) {
		String sortedCharsStr=sortedChars(arr[idx]);
		if ( sortedCharAnagrams.contains(sortedCharsStr)) {
			anagrams.add(arr[idx]);
		}
	}
	String[] retVal=new String[anagrams.size()];
	int idx=0;
	Iterator itr=anagrams.iterator();
	while (itr.hasNext()) {
		retVal[idx]=(String)itr.next();
		idx++;
	}
	return retVal;
}

Click here to download and run code and test cases !

Below fully running code can be copied and run on Eclipse or other Java IDEs. Refer the classname in code below. If the class name below is "A", save the code below to a file named A.java before running it. Be sure to try your own test cases to enhance your understanding ! You can also tweak the code to optimize or add enhancements and custom features.

import java.util.Arrays;
import java.util.HashSet;
import java.util.Iterator;


public class SetFindAnagrams {
	
public String[] setFindAnagrams(String[] arr) {
	HashSet<String> wordsHash=new HashSet<String>();
	HashSet<String> sortedCharAnagrams=new HashSet<String>();
	HashSet<String> anagrams=new HashSet<String>();
	for (int idx=0; idx< arr.length; idx++) {
		String sortedCharsStr=sortedChars(arr[idx]);
		if (! wordsHash.contains(sortedCharsStr)) {
			wordsHash.add(sortedCharsStr);
		}else {
			sortedCharAnagrams.add(sortedCharsStr);
		}
	}
	for (int idx=0; idx< arr.length; idx++) {
		String sortedCharsStr=sortedChars(arr[idx]);
		if ( sortedCharAnagrams.contains(sortedCharsStr)) {
			anagrams.add(arr[idx]);
		}
	}
	String[] retVal=new String[anagrams.size()];
	int idx=0;
	Iterator itr=anagrams.iterator();
	while (itr.hasNext()) {
		retVal[idx]=(String)itr.next();
		idx++;
	}
	return retVal;
}

		


public String sortedChars(String str) {
	char[] chars=str.toCharArray();
	Arrays.sort(chars);
	return new String(chars);
}


	
public static void main(String[] args) {
		
	SetFindAnagrams sp=new SetFindAnagrams();
	String[] retVal;
	
	try {
	String[] strArray1 = {"listen", "near", "swim", "morning", "silent"};
	printArraySummary(strArray1, "Original Array");
	retVal=sp.setFindAnagrams(strArray1);
	printArraySummary(retVal, "Word with Anagrams in array");
			
	String[] strArray2 = {"pins", "road", "ate", "eat", "tree", "spin", "tree"};
	printArraySummary(strArray2, "Original Array");
	retVal=sp.setFindAnagrams(strArray2);
	printArraySummary(retVal, "Word with Anagrams in array");
			
	String[] strArray3 = {"join", "roar", "smile", "art", "more", "dear", "pen"};
	printArraySummary(strArray3, "Original Array");
	retVal=sp.setFindAnagrams(strArray3);
	printArraySummary(retVal, "Word with Anagrams in array");
			
	String[] strArray4 = {"pat", "bare", "tap", "bear"};
	printArraySummary(strArray4, "Original Array");
	retVal=sp.setFindAnagrams(strArray4);
	printArraySummary(retVal, "Word with Anagrams in array");
			
	}catch (Exception exception) {
	System.out.print("Exception,"+ exception);
	exception.printStackTrace();
				
	}
}
			
public static void printArraySummary(String[] intArray, String label) throws Exception {
   	// Case 1: The input Array is null !!
	if (intArray == null) { System.out.println("\n\n Input Array was null !! \n"); return; }
	// Case 2: Print input Array by index (first to last)
	System.out.println();
	System.out.println("************************************************************************");
	System.out.print(label+" : ");
	int arrayIndex=0;
	for (arrayIndex=0; arrayIndex< intArray.length; arrayIndex++) {
			System.out.print(intArray[arrayIndex]);
			if (arrayIndex< intArray.length-1) {System.out.print(",");}
	} 
	System.out.println();
	System.out.println("*************************************************************************");
	System.out.println();
	Thread.sleep(2000);
	return;
}			
		
		

}