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?