Form a word from a scrambled letters in java

Question

i'm doing a game project,in which we have to form words dynamically with the given set of letters... the given set of letters may contain duplicate also.. while forming words we can use a letter from a given set of letters for any number of times(say for twice or thrice)... help me with an algorithm to form all possible meaningful words from the given set

Thank u all

Answer 1

The simple approach is to create every possible ordering of letters, then compare each one of them to your dictionary.

You can refine it a bit by storing the dictionary in a data structure which facilitates quick lookups. (hash table, tree, etc) I've been meaning to implement a 28-ary tree for quick dictionary word access, but haven't got around to it yet.

Answer 2

I did something similar for a crossword solver many moons ago. I basically took a dictionary file and modified it so it looked like:

aardvark:aaadkrr
albatross:aablorsst

Then, for a given set of letters, I could just sort them and use something like:

grep ':{sorted letters}$' mywords.txt | sed 's/:.*$//'

and that would give me the candidate words.

You'll have to wrap some permutation/combination code around that if you're looking for words that can use less than the full set, but the algorithm given was very efficient.

For Java, I'd consider either maintaining a hash table in-memory (assuming you have space) or using an external database where the lookup keys are the sorted varaiations, allowing duplicates of course, since pore and rope would both come from eorp.

While my grep-based solution was fine for my own purposes, you probably don't want to rely on external tools and sub-processes in a robust application.