Anagrams pairs

[Tushar Goel]

I am working on a problem where i have to find all the possible anagram pairs from the given file input. I have written a code for the same but it is working very slow.
Any idea what i am doing wrong:

	public Map<String, List<String>> isAnagram(String inputTxt) throws IOException {
		if (isNull(inputTxt) || isLengthZero(inputTxt)) {
			throw new IllegalArgumentException();
		}

		long startTime = System.currentTimeMillis();
		SortedSet<String> sortedSet = readInput(inputTxt);

		Map<String, List<String>> anagramPairs = new HashMap<>();
		while (!sortedSet.isEmpty()) {
			//get first element to compare
			String node = sortedSet.first();
			findAnagramPairs(sortedSet, anagramPairs, node);

			//all the anagra pair for given node
			List<String> pairs = anagramPairs.get(node);

			//remove all the existing anagram pairs for the given node from the
			//input to avoid reading again as those pairs are already anagram with
			//each other.
			if (pairs != null ) {
				sortedSet.removeAll(pairs);
			}
		}
		System.out.println("Time: " + (System.currentTimeMillis() - startTime));
		return anagramPairs;
	}

	private SortedSet<String> readInput(String inputTxt) throws IOException {
		BufferedReader bis = new BufferedReader(new FileReader(inputTxt));
		String input = null;
		SortedSet<String> sortedSet = new TreeSet<>();

		while ((input = bis.readLine()) != null) {
			sortedSet.add(input);
		}
		System.out.println("Size: " + sortedSet.size());
		bis.close();
		return sortedSet;
	}

	private void findAnagramPairs(SortedSet<String> sortedSet,
			Map<String, List<String>> anagramPairs, String node) {

		for (String temp : sortedSet) { 
			if (!node.equals(temp)) { //avoid checking for itself
				boolean isAnagram = isAnagram(node, temp);
				storeAndUpdateAnagramPairs(anagramPairs, node, temp, isAnagram);
			}
		}
	}

	private void storeAndUpdateAnagramPairs(
			Map<String, List<String>> anagramPairs, String node, String temp,
			boolean isAnagram) {
		if (isAnagram) {
			if (anagramPairs.containsKey(node)) {
				anagramPairs.get(node).add(temp);
			} else {
				anagramPairs.put(node, new ArrayList<>());
			}
		}
	}


	private boolean isLengthZero(String inputTxt) {
		return (inputTxt == null) ? true : inputTxt.trim().length() == 0;
	}

Note: In another forum here, i have not pasted this part and dint ask same question. In this
i have asked question on "isAnagram()" method , i used in line 50.

[Mike. J. Thompson]

When you say its working very slowly, do you mean it returns a result but takes along time or it keeps running and never returns a result?

If its the latter then I think I see a bug in the while loop in isAnagram(). If the string is matched with an anagram you remove it from the set, but if its not you leave it in the set. This means that if any word doesn't have a matching anagram you will pull that same word from the set on the next loop and check it again. This will go on forever.

If you meant the former then you will need to profile the code using a profiler and find the bottleneck.

[Tushar Goel]

Thanks Mike, Actually, it was case 2. Result was not coming even after long time.

I figured it out now, issue was with the while loop condition. I changed it and it worked fine now. Updated is as below:

public Map<String, List<String>> isAnagram(String inputTxt) throws IOException {
		if (isNull(inputTxt) || isLengthZero(inputTxt)) {
			throw new IllegalArgumentException();
		}

		long startTime = System.currentTimeMillis();
		SortedSet<String> sortedSet = readInput(inputTxt);

		Map<String, List<String>> anagramPairs = new HashMap<>();
		int items = 0;
		int size = sortedSet.size();

		while (items <= size) {
			//get first element to compare
			String node = sortedSet.first();
			findAnagramPairs(sortedSet, anagramPairs, node);
			//all the anagram pair for given node
			List<String> pairs = anagramPairs.get(node);

			items++;

			//remove all the existing anagram pairs for the given node from the
			//input to avoid reading again as those pairs are already anagram with
			//each other.
			if (pairs != null ) {
				sortedSet.removeAll(pairs);
			} else {
				sortedSet.remove(node);
			}
		}
		System.out.println("Time: " + (System.currentTimeMillis() - startTime));
		return anagramPairs;
	}

But even after this, it slow. For example, for around 3000 i/p it took 9 sec but for others it was mentioned that for 10,000 input it took 2 sec. Any thought of improvement.

[Carey Brown]

For performance improvements you may need to redesign your approach. Given that an anagram has the same letters but not in the same order, you can make a "key" for each word by making a string of the same letters where the letters are sorted in alphabetical order. Then you create a HashMap based on those keys. The HashMap would then contain a HashSet instead of a List so that no word is entered twice. In this way you can avoid the multiple comparisons of each word. Then, you'd have an anagram when the Set contained two or more words. This would also avoid the need for a sorted set.

Can you post your test set somewhere?

[Carey Brown]

On line 47 the call to isAnagram() is being passed two Strings but the method only takes one String. Did you post your latest code?

[Tushar Goel]

My complete code is as below:

package main.example.anagrams;

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.SortedSet;
import java.util.TreeSet;
import java.util.regex.Pattern;

public class Anagram {

	private static final String REGEX = "[a-zA-Z\\s+]+";

	public Anagram() {

	}

	public boolean isAnagram(final String compareTo, final String compareWith) {
		return isValidInput(compareTo, compareWith);
	}

	private boolean isValidInput(String compareTo, String compareWith) {
		boolean isValid = true;

		if (isInputNull(compareTo, compareWith)) {
			return false;
		}

		compareTo = removeAllSpacesAndConvertToLowerCase(compareTo);
		compareWith = removeAllSpacesAndConvertToLowerCase(compareWith);

		if (isInputEmpty(compareTo, compareWith)) {
			isValid = false;
		} else if (!isInputLengthMatches(compareTo, compareWith)) {
			isValid = false;
		} else if (!isInputContainsOnlyAlphabets(compareTo, compareWith)) {
			isValid = false;
		} else if (!isCharactersMatchesBetweenInput(compareTo, compareWith)) {
			isValid = false;
		} else if (!isCharactersFrequencyMatches(compareTo, compareWith)) {
			isValid = false;
		}
		return isValid;
	}


	private boolean isInputNull(final String compareTo, final String compareWith) {
		return isNull(compareTo) || isNull(compareWith);
	}

	private boolean isNull(final String input) {
		return input == null;
	}

	private String removeAllSpacesAndConvertToLowerCase(final String compareTo) {
		return toLowerCase(compareTo).replaceAll("\\s+", "");
	}

	private String toLowerCase(final String compareTo) {
		return compareTo.toLowerCase();
	}

	private boolean isInputEmpty(final String compareTo, final String compareWith) {
		return (length(compareTo) == 0) || (length(compareWith) == 0);
	}

	private boolean isInputLengthMatches(final String compareTo,
			final String compareWith) {
		return length(compareTo) == length(compareWith);
	}

	private int length(final String input) {
		return input.length();
	}

	private boolean isInputContainsOnlyAlphabets(final String compareTo,
			final String compareWith) {
		return isAlphabets(compareWith) && isAlphabets(compareTo);
	}

	private boolean isAlphabets(final String input) {
		return Pattern.matches(REGEX, input);
	}

	private boolean isCharactersMatchesBetweenInput(final String compareTo,
			final String compareWith) {

		boolean isMatched = true;
		for (int i = 0; i < length(compareTo); i++) {
			String substring = substring(compareTo, i);
			if (!isSubstringMatches(compareWith, substring)) {
				isMatched = false;
				break;
			}
		}
		return isMatched;
	}

	private String substring(final String compareTo, final int i) {
		return compareTo.substring(i, i + 1);
	}

	private boolean isSubstringMatches(final String compareWith,
			final String substring) {
		return compareWith.contains(substring);
	}

	private boolean isCharactersFrequencyMatches(final String compareTo,
			final String compareWith) {
		Map<String, Integer> charactersMap1 = mapToHaveFrequencyOfEachCharacter(compareTo);
		Map<String, Integer> charactersMap2 = mapToHaveFrequencyOfEachCharacter(compareWith);

		return isCharactersFrequencyMatches(charactersMap1, charactersMap2);
	}



	private Map<String, Integer> mapToHaveFrequencyOfEachCharacter(
			final String compareTo) {
		Map<String, Integer> map = new HashMap<>();
		int length = length(compareTo);
		for (int i = 0; i < length; i++) {
			String key = substring(compareTo, i);
			updateMap(map, key);
		}
		return map;
	}

	private void updateMap(final Map<String, Integer> map, final String key) {
		if (map.containsKey(key)) {
			updateFrequency(map, key);
		} else {
			insertKey(map, key);
		}
	}

	private void updateFrequency(final Map<String, Integer> map, final String key) {
		Integer frequency = map.get(key);
		map.put(key, frequency + 1);
	}

	private void insertKey(final Map<String, Integer> map, final String key) {
		map.put(key, 1);
	}

	private boolean isCharactersFrequencyMatches(
			final Map<String, Integer> charactersMap1,
			final Map<String, Integer> charactersMap2) {

		boolean isMatched = true;
		for (String key : charactersMap1.keySet()) {
			if (!isFrequencyMatches(charactersMap1, charactersMap2, key)) {
				isMatched = false;
				break;
			}
		}
		return isMatched;
	}

	private boolean isFrequencyMatches(final Map<String, Integer> charactersMap1,
			final Map<String, Integer> charactersMap2, final String key) {
		return charactersMap2.get(key) == charactersMap1.get(key);
	}

	public int testInputSize() {
		return 0;
	}

	public Map<String, List<String>> isAnagram(String inputTxt) throws IOException {
		if (isNull(inputTxt) || isLengthZero(inputTxt)) {
			throw new IllegalArgumentException();
		}

		long startTime = System.currentTimeMillis();
		SortedSet<String> sortedSet = readInput(inputTxt);

		//System.out.println("input: " + sortedSet);
		Map<String, List<String>> anagramPairs = new HashMap<>();
		int items = 0;
		int size = sortedSet.size();

		while (!sortedSet.isEmpty()) {
			//get first element to compare
			String node = sortedSet.first();
			findAnagramPairs(sortedSet, anagramPairs, node);
			//			System.out.println(anagramPairs);
			sortedSet.remove(node);
			//all the anagram pair for given node
			List<String> pairs = anagramPairs.get(node);

			//remove all the existing anagram pairs for the given node from the
			//input to avoid reading again as those pairs are already anagram with
			//each other.
			if (pairs != null ) {
				sortedSet.removeAll(pairs);
			}
		}
		System.out.println("Time: " + (System.currentTimeMillis() - startTime));
		return anagramPairs;
	}

	private SortedSet<String> readInput(String inputTxt) throws IOException {
		BufferedReader bis = new BufferedReader(new FileReader(inputTxt));
		String input = null;
		SortedSet<String> sortedSet = new TreeSet<>();

		while ((input = bis.readLine()) != null) {
			sortedSet.add(input);
		}
		System.out.println("Size: " + sortedSet.size());
		bis.close();
		return sortedSet;
	}

	private void findAnagramPairs(SortedSet<String> sortedSet,
			Map<String, List<String>> anagramPairs, String node) {

		for (String temp : sortedSet) { 
			if (!node.equals(temp)) { //avoid checking for itself
				boolean isAnagram = isAnagram(node, temp);
				storeAndUpdateAnagramPairs(anagramPairs, node, temp, isAnagram);
			}
		}
	}

	private void storeAndUpdateAnagramPairs(
			Map<String, List<String>> anagramPairs, String node, String temp,
			boolean isAnagram) {
		if (isAnagram) {
			if (anagramPairs.containsKey(node)) {
				anagramPairs.get(node).add(temp);
			} else {
				List<String> elements = new ArrayList<>();
				elements.add(temp);
				anagramPairs.put(node, elements);
			}
		}
	}


	private boolean isLengthZero(String inputTxt) {
		return (inputTxt == null) ? true : inputTxt.trim().length() == 0;
	}
}

[Carey Brown]

Thanks.

[Tushar Goel]

Your approach looks better than me. Are you saying like below:

Map<String, Set<String>> map = .....

foreach A <- inputs
     temp <- convert A into char array
     key <- sort char array and create a string
     if (map contains key)
             add the A as a value of the key into the map
     else
             add key as the map key and new hash set
     

[Carey Brown]

Tushar Goel wrote:Your approach looks better than me. Are you saying like below:

Map<String, Set<String>> map = .....

foreach A <- inputs
     temp <- convert A into char array
     key <- sort char array and create a string
     if (map contains key)
             add the A as a value of the key into the map
     else
             add key as the map key and new hash set
     

Yes, I think you've got the idea.
I'd still be interested in a test data set of 30,000.

[Tushar Goel]

I will make changes as per new approach and let you know. My current approach will definitely takes several minutes.