Home > Computer Programming > Finding Anagrams

Finding Anagrams

January 21, 2013 Leave a comment Go to comments

This week we looked at creating a method in Java to see if two words were anagrams. Most of you set up nested loops to check if all the characters in one word were in the other word. Here is the general algorithm in pseudocode:

loop i from 0 to S1.length()
 if S2.indexOf(S1.charAt(i)) = -1 then
  return false
 end if
end loop
return true

This will detect anagrams, but it also detects “false positives”, for instance the algorithm will say that the following two strings are anagrams, when they are clearly not:

S1 = "RODEO"
S2 = "DOER"

And even if you do a check for the same number of characters, you will still have problems with:

S1 = "DOOR"
S2 = "DOER"

The problem is that the algorithm only checks that all characters in S1 are in S2, and that is not enough.

One solution is to sort both words and then compare them. This method never gives false positives but sorting is computationally expensive. The question is, what is the most efficient way of determining if two strings are anagrams?

Advertisements
  1. No comments yet.
  1. No trackbacks yet.

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