Win a copy of The Java Performance Companion this week in the Performance forum!
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

Finding anagrams in a dictionary file using pre-fixes

 
Joanna Spence
Greenhorn
Posts: 23
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 12145
30
Chrome Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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?

 
Pradeep Katipamula
Ranch Hand
Posts: 37
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 23
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 12145
30
Chrome Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 37
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Ah.. I understood a bit this time.
Elmira, I will try to get you the code.
 
fred rosenberger
lowercase baba
Bartender
Posts: 12145
30
Chrome Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 37
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic