File APIs for Java Developers
Manipulate DOC, XLS, PPT, PDF and many others from your application.
http://aspose.com/file-tools
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

finding anagrams

 
Vidya Ramachandran
Greenhorn
Posts: 24
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Eclipse IDE Hibernate Java
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
You could do something like this:

[ March 16, 2007: Message edited by: Garrett Rowe ]
 
Vidya Ramachandran
Greenhorn
Posts: 24
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
wouldnt that involve too many comparisons Garrett Rowe? is there a better solution?
 
Stan James
(instanceof Sidekick)
Ranch Hand
Posts: 8791
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
thanks stan james
 
Consider Paul's rocket mass heater.
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic