3

I am trying to create this app on the iphone that given 6 letters, it would output all the possible 3-6 letter english words. I already have a dictionary, I just want to know how to do it.

I searched around and only found those scrabble solvers in python or those word search grid solutions.

I think a brute force search would do, but I'm concerned about the performance. Code is not necessary, a link to an algorithm or the algorithm itself would be fine, I think I'll be able to manage once I get that.

Thanks!

Brad Larson
  • 170,088
  • 45
  • 397
  • 571
kazuo
  • 297
  • 1
  • 6
  • 15

3 Answers3

1

If you're concerned about performance, this method might do the trick. It involves some preprocessing but would allow for nearly-instantaneous lookup for anagrams.

  1. Create a data structure that maps a String key to a List of Strings (I'm more familiar with Java, so in that case it would be a Map<String,List<String>>) This will store your dictionary.

  2. Define a function that takes a string and outputs the same letters arranged alphabetically. For example, hello would become ehllo; kitchen would become cehiknt. I'll refer to this function as keyify(word)

  3. Here's the preprocessing part: for each item in your dictionary, find the list for that item's key (keyify(item)) and add that item to the list.

  4. When it comes time to look up anagrams of a given word, just look up the list at they keyify of that word. For example, if the input was kitchen, the keyify would be cehiknt, and looking that up in your map should result in a list containing kitchen, chicken and whatever other anagrams of kitchen that I forgot :P

Dylan
  • 13,645
  • 3
  • 40
  • 67
  • Great solution, similar to tassainari's link to J. Cohen's answer. I think the part that I would have a problem would be building up that Map, since the resulting words should be from 3-6 letters. :S At this point, I am confused on how to implement. – kazuo Jul 27 '11 at 03:26
  • You could pretty easily limit which items from the original dictionary you put into the lookup map. No reason to put in data that you don't need. As for implementation, I'm not familiar with objective C so I can't help you there. – Dylan Jul 27 '11 at 03:29
0

Check out this answer: Algorithm to generate anagrams.. Look at the answer by Jason Cohen. Alphabetize the 6 letter word, then run through your dictionary and alphabatize that word and compare.

Community
  • 1
  • 1
tassinari
  • 2,313
  • 2
  • 24
  • 32
0

I actually ran into this issue a few weeks back and the most efficient way I could figure out how to solve it was

I found all the subsets of a given string (this will take O(2^n) )

Then I looked at my dictionary to see if the subset "used up" all the characters of all the strings of that size

for example given the string "hetre" and the words "the, there, her" are in your dictionary you can calculate all subsets

{h}{e}{t}{r}{e}{he}{ht}{hr}{he}{het}{her}{reh}... there are 32 subsets of "hetre"

then check to see if any of these subsets are similar to the words in the dictionary in this case reh is similar to her which means that her is a word to be used

This was the most efficient way I could think of

research PowerSets and think of a way you could write the function that "uses up" the strings

Another way would be to brute force it by figuring out the powersets for the strings and finding all permutations, this will destroy performance

Mine didn't give me problems till I started entering strings over 15 characters using the first method using the second method I didn't get problems till 7

dbarnes
  • 1,803
  • 3
  • 17
  • 31
  • I was wondering, which would be a more practical solution, doing the powerset of the string or finding all the combinations/permutations? – kazuo Jul 27 '11 at 08:37
  • you'd have to find the powerset of the strings then checking all the strings then find all the combinations and permutations, the power set will find all strings of all sizes where the permutations will only give strings of the same size – dbarnes Jul 27 '11 at 18:51