Code Puzzle: Anagram Detector III

We have been looking at different approaches to detect anagrams given two strings. In our first detector we repeatedly scanned the strings counting and comparing the occurrences of each character. In our second detectort we sorted each string and compared them to each other. In this third attempt will will look at a more efficient technique.

As usual the complete runnable source is on github.

Let’s take another look at the scanning technique. This approach suffers from the problem of repeated scans. There is an underlying scan to get the unique characters, and then a separate scan for each character. Every time there is a scan and we read a character without doing anything with it, we are passing over the opportunity to use information that is available to us. To remedy this, we can actually analyse each string with a single scan.

To accomplish this, we can store the information about what we see as we scan each character for each string. The best way to store this information is in a map from each character to the number of times we’ve seen that character. For each character that we come across, we just need to increment the count for that character. After we’ve scanned both strings, all we need to do is compare the maps to see if the two strings are anagrams.

Consider the following code:

public class AnagramDetectorFrequencyMap implements AnagramDetector {

   @Override
   public boolean isAnagram(String input1, String input2) {

      // null check and length check omitted for conciseness...

      List<Character> input1Set = toCharacters(input1.toLowerCase());
      List<Character> input2Set = toCharacters(input2.toLowerCase());

      return createFrequencyMap(input1Set).equals(createFrequencyMap(input2Set));
   }

   private Map<Character, Integer> createFrequencyMap(List<Character> inputs) {
      // the count of character appearances
      Map<Character, Integer> frequencies = new HashMap<>();
      for(Character c : inputs) {
         Integer count = frequencies.get(c);
         count = (count == null) ? 0 : count;
         frequencies.put(c, count + 1);
      }
      return frequencies;
   }

   private List<Character> toCharacters(String input) {
      return Arrays.asList(ArrayUtils.toObject(input.toLowerCase().toCharArray()));
   }

}

The best part is that the processing time grows linearly with string size, this is an O(N) solution which is the lowest we are going to get for this particular problem.

Hopefully the anagram exercises were fun and informative! A possibility for follow up versions of the exercise could be to write a functional version with lambdas in Java 8. More on that later…