Thread: Words in a Word

Anagram detection is usually done by converting the things to be compared into a form that is ignorant of the letter ordering. One way to do this is by simply rearranging the letters into a single standard form, e.g. by sorting them. If two words have the same standard form, they are anagrams.

You also take your database and preprocess it by building a map from each standard form to all the words that reduce to it.

Finding every possible rearrangement is far too slow. We're talking about heat death of the universe too slow.

Deleting characters is also done on the standard form. When deleting from the standard form, be sure to skip redundant deletions, e.g. the standard form of anagram is aaagmnr - there's no difference in which a you delete, so only do it once. It may help you to use a standard form that encodes letters just once, remembering their count, i.e. the standard form becomes 3a1g1m1n1r.