Code Puzzle: Anagram Detector II

In the last post, we looked at the anagram detector and a solution. This is a nice problem with a few solutions, so let’s take a look at some more.

Another approach as an alternative to looping is to take advantage of the information we have given the nature of anagrams.

We know before we start that a string is an anagram of another if its letters can be arranged to form the other string. So another approach is to actually rearrange the letters and see if we can form the one string from the other. Equivalently, we could also rearrange the letters of both strings to see if each can be made to equal a third string. In that case the transitive property of anagrams would show that the two original inputs are anagrams. We can define this third string to be the string with sorted characters. In other words: sort the two input strings and see if the sorted strings are equal.

public class AnagramDetectorSorting implements AnagramDetector {
   @Override
   public boolean isAnagram(String input1, String input2) {

      char[] input1Chars = input1.toLowerCase().toCharArray();
      char[] input2Chars = input2.toLowerCase().toCharArray();
      Arrays.sort(input1Chars);
      Arrays.sort(input2Chars);
      return Arrays.equals(input1Chars, input2Chars);
   }
}

One clear advantage of this is conciseness and clarity. There are no loops, there is nothing complicated enough to even require a comment. Unfortunately this may be the least efficient of the approaches. Many popular sorting algorithms (e.g. merge sort and quicksort) are O(n log(n)). In the next blog post we will see a more efficient approach.

Advertisements

Leave a comment

Filed under Software Engineering

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s