Win a copy of Penetration Testing Basics this week in the Security forum!

# finding anagrams

Vidya Ramachandran
Greenhorn
Posts: 24
given an array of say 10 words, how to display the anagrams from the list provided.

Eg: pat and tap, scared and scacred etc

Paul Sturrock
Bartender
Posts: 10336
The hard part of this is how to infom your program what constitutes a valid English word. What you need is some sort of dictionary resource to supply your list of valid words. Have a google for Java spell checkers. These always have such a thing.

(Note: Your second example is not an anagram)

Vidya Ramachandran
Greenhorn
Posts: 24
thanks for your response paul. in the second example, i meant scared and sacred..sorry about the typo! i have figured out a method to find anagrams. first we alphabetically sort each word in the list. then we sort the list itself so that anagrams are together. but then how to establish which jumbled word corresponds to the original word? can some please help me to code this.

eg : original list :- scared,take,pack,sacred,pat,tap
sorting each word gives :- acders,aekt,ackp,acedrs,apt,apt
sorting the list gives :- acders,acders,ackp,aekt,apt,apt
how to establish that the two acedrs gives scared and scared. also the two apt corresponds to pat and tap

Garrett Rowe
Ranch Hand
Posts: 1296
You could do something like this:

[ March 16, 2007: Message edited by: Garrett Rowe ]

Vidya Ramachandran
Greenhorn
Posts: 24
wouldnt that involve too many comparisons Garrett Rowe? is there a better solution?

Stan James
(instanceof Sidekick)
Ranch Hand
Posts: 8791
Maybe a "multi map" ... Work through the input list and make a Map with key = sorted value and value is a List of words that give the same sorted result. (We already know they are anagrams of each other.)

Key = acders
Value = List { sacred, scared }

Then you can sort each dictionary word and see if it's in the map.

I'd be tempted to take a totally different approach ... use recursion to try all possible shufflings of the letters in each input word, compare those to valid words in the dictionary. A Ternary Search Tree could make the dictionary search very fast and you could check each letter as you go as part of the recursive routine. If that made no sense at all, please stick with what you have.

Vidya Ramachandran
Greenhorn
Posts: 24
thanks stan james