I am creating an app where the user enters 8 characters. After he enters the string I have to see if it is an eight letter word. If not, check if contains a seven letter word etc.
I am checking against a given pool of 150k+ words. I only care about the longest possible match. Is there a better way then this one:
- WordPool.Contains(word.substring(0,8))
- WordPool.Contains(word.substring(0,7)),
WordPool.Contains(word.substirng(1,7)) - WordPool.Contains(word.substring(0,6)),
WordPool.Contains(word.substirng(1,6)),
WordPool.Contains(word.substirng(2,6)) - etc…
Edit
I forgot to add that I am checking against an english dictionary.
So far I am using this:
for(i = 8; i >= 3; i--)
for(j = 0; j <= 8 - i; j++)
if(words.contains(word.substring(j, i))
//do something
Edit 2
I have been using the approach defined above just with a minor change. I am using a few background agents which all search for a word of a certain length. They all then return a result and I just pick the one which gives the user the highest score.
10
Preprocessing your word pool into a trie would make the longest search easy. Just traverse the trie until you can’t go any further. You’d still have to try it for each starting position, though. For example:
wordPool.longestMatch("deadbeef");
wordPool.longestMatch("eadbeef");
wordPool.longestMatch("adbeef");
wordPool.longestMatch("dbeef");
wordPool.longestMatch("beef");
wordPool.longestMatch("eef");
wordPool.longestMatch("ef");
wordPool.longestMatch("f");
You could also short-circuit if you already found a match longer than the length of the remaining subsequences. The example would find “dead” on the first line, and “beef” on the fifth line, so you could automatically skip the last three subsequences.