File APIs for Java Developers
Manipulate DOC, XLS, PPT, PDF and many others from your application.
http://aspose.com/file-tools
The moose likes Java in General and the fly likes Finding anagrams in a dictionary file using pre-fixes Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Java in General
Bookmark "Finding anagrams in a dictionary file using pre-fixes" Watch "Finding anagrams in a dictionary file using pre-fixes" New topic
Author

Finding anagrams in a dictionary file using pre-fixes

Joanna Spence
Greenhorn

Joined: May 31, 2010
Posts: 23
Hello,

I need to write a method in a java class that finds the anagrams of a word in a dictionary file using prefixes.

I started this way with a method that finds all the permutations and then a method to go through each character.

Here's how I think it should work and then I don't think my code is matching up...

-take the word, search on the first character,
if match for first letter
continue to next letter
if not backtrack and then skip to next letter...

here's what i have and I need some more direction:
thanks...


fred rosenberger
lowercase baba
Bartender

Joined: Oct 02, 2003
Posts: 10916
    
  12

Why do you think your code is not doing what you want? What IS it doing/doing differently?

I'm not sure what you mean by 'using pre-fixes' - can you elaborate?

I don't understand your algorithm.

'take the word, search on the first character' - take WHAT word, and search WHAT for the first character? Are you going through the dictionary and seeing if a word matches your input word, or are you taking your input word and seeing if it matches each dictionary word?

And what do you mean by 'backtrack'?

in either case, I don't see how this works. You need to see if each letter in word 'A' is in word 'B', and possible make sure you account for multiple. In other words, if word 'A' has 3 's' characters, does word 'B' need to have exactly 3 's' characters?


There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors
Pradeep Katipamula
Ranch Hand

Joined: May 11, 2010
Posts: 37
I too agree with Fred. I dint understand
Elmira, instead of talking abt the code, can you first explain the algorithm you want to develop.

Pradeep
Joanna Spence
Greenhorn

Joined: May 31, 2010
Posts: 23
I have to take a word from a test file,
for instance
the word "razibar"

and search a dictionary of words to find anagrams for razibar.

An easy way would be to get all the permutations of the word "razibar" and compare them to the dictionary, but I have to search based on prefixes.

For instance...
Are there any words that start with "r"
if yes, then add the "a" to the prefix, if yes, add "z", "i" and so on until you have a match or you do not

then if there is not a match for that prefix for example, "raz", then remove the "z" and then search on "rai" and so on...

i'm not sure how to implement this.

fred rosenberger
lowercase baba
Bartender

Joined: Oct 02, 2003
Posts: 10916
    
  12

that makes a little more sense.

What you're basically doing is building an N-tree. your root node has nothing in it. Each time you go down a level, you add a letter. So, start with your root node - it's empty. Are there any words that match "*"? all of them do.

Build your first child node - "r". Are there any words that start with "r*"? yes.

build your first child node - "ra" Are there any words that start with that? yes.

build your first child node - "raz"...etc.

eventually, you'll get to "razibar" It will pass. build your child node - oops!!! no more letters. go up one level

build the next child for "raziba" - we already used the 'r', so...we're done here. go up...

"razib" - we already used the 'a', so now use the 'r', giving "razibr"



at each level, check to see if there is a matching word in the dictionary. If so, you build and test all the children. if not, you can jump up a level and build that node's next child.

If a node has no children, you need to report it. BUT...if a node DOES have children, you MAY need to report it... I.e. if your original word was "sheep", you need to report "she", even though it has children.
Pradeep Katipamula
Ranch Hand

Joined: May 11, 2010
Posts: 37
Ah.. I understood a bit this time.
Elmira, I will try to get you the code.
fred rosenberger
lowercase baba
Bartender

Joined: Oct 02, 2003
Posts: 10916
    
  12

Pradeep Katipamula wrote:Elmira, I will try to get you the code.

Please don't give the O.P. the code. This is clearly a homework assignment. The best way for anyone to learn is to do it themselves.

Also, many schools would frown upon a student turning in work done by someone else, and could even expel them. Even if all they did was look at your source to write their own, it would have the appearance of impropriety.
Pradeep Katipamula
Ranch Hand

Joined: May 11, 2010
Posts: 37
I'd actually come to post the solution.
@Fred, you are right!! I was just enthusiatic about writing some logic Generally we dont get chance to write some logically code during our normal work, its all those boring stuff. Atleast, I don't get a chance
@Elmira: I hope you could figure out from what Fred has said.
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Finding anagrams in a dictionary file using pre-fixes
 
Similar Threads
ignoring space in an anagram solver
Regarding remove word in a string
Convert a string into an array of String
cutting string into peaces
Generating all the permutations nad combinations of the given alphabets