Finding Anagrams

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?

Leave a Reply

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

You are commenting using your 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 )

Connecting to %s