Objective-C jumbled letters solver

I am trying to create this app on the iphone that given 6 letters, it would output all the possibl开发者_如何学Pythone 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!

---

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

---

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.

---

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