I'm Making a an ios application where you input 9 lettes and it will output anagrams of those 9 letters. It is like the target word, or 9 letter word in the paper. Like this link:
http://nineletterword.tompaton.com/
It doesn't just provide anagrams for 9 letters, it will do it for 4 letters, 5 letters, 6 letters... all of which contain at least the middle letter.
I want to make it an offline application, so I don't want to reference any websites or use an online json...
How would I go about checking if an array of the 9 letters can be rearranged into a word which is in an English dictionary which I have downloaded.
E.g. I have the input of (a,b,a,n,D,o,n,e,d): how would I get the output of 4 letters or more that are English words in an array called "English Dictionary" which must contains the middle letter "D" - like "abandon", "bond", "dead"...
Is the best method lots and lots of loops and if statements or is there something in xcode/ objective c which I can use to just get the list of 4 letters and then have all possible arrangements of it...
Cheers
Let me propose a different algorithm that depends on a lookup, not a search through an array.
Setup:
Iterate over the words in the dictionary. For each word, create a string with the same characters, sorted alphabetically. Using this string as a key, create a dictionary of arrays of the original words.
Usage:
Now You can do the check on any character combination very quickly: Just sort the characters like above and look the resulting key up in the map.
Example:
original array:
( bond, Mary, army )
anagram lookup map:
Using this map it's very fast to check anagrams of any word. No iteration over the dictionary array is needed.
Edit:
My proposed algorithm splits in three parts:
anagramMap
anagramKey
findAnagrams
.Here's an implementation of all three methods as a category on
NSString
:Assuming a test string in a variable called
nineletters
you would log the possible values using:First you need a method to check if one word is an anagram of a second word. There are many possible solutions (search for "Objective-C anagram"). This is essentially the method from https://stackoverflow.com/a/13465672/1187415, written slightly differently:
Examples:
[self does:@"abandoned" contain:@"bond"] = YES
[self does:@"abandoned" contain:@"sea"] = NO
, because there is no "s" in the first word.[self does:@"abandoned" contain:@"noon"] = NO
, because "noon" has 2 letters "o", but the first word has only one "o".Then you can proceed as follows: