Predicting words based on swiping a keyboard I thought this question was particularly interesting DailyProgrammer 284: Wandering Fingers so thought I'd have a pop at it myself. See the other question for the nitty gritty but the brief problem statement is:


  You'll be given a string of characters representing the letters the user has dragged their finger over.
  
  For example, if the user wants "rest", the string of input characters might be "resdft" or "resert".
  
  Input
  
  Given the following input strings, find all possible output words 5 characters or longer.
  
  
  qwertyuytresdftyuioknn  
  gijakjthoijerjidsdfnokg
  
  
  Output
  
  Your program should find all possible words (5+ characters) that can be derived from the strings supplied.
  
  Use http://norvig.com/ngrams/enable1.txt as your search dictionary.
  
  The order of the output words doesn't matter.
  
  
  queen question
  gaeing garring gathering gating geeing gieing going goring
  


I've made the assumption that this is the English alphabet (i.e. [a-z]) which is pretty normal for a qwerty keyboard.

I created a simple lookup class:

public class AutocompleteCache
{
    private readonly IList&lt;string&gt;[] cache = new IList&lt;string&gt;[26*26]; 

    public AutocompleteCache(IEnumerable&lt;string&gt; wordList)
    {
        if (wordList == null)
        {
            throw new ArgumentNullException(nameof(wordList));
        }
        foreach (var word in wordList.Where(w =&gt; w.Length &gt;= 5))
        {
            var index = CalculateIndex(word);
            var cachedWords = cache[index];
            if (cachedWords == null)
            {
                cache[index] = new List&lt;string&gt;();
            }
            cache[index].Add(word);
        }
    }

    private static int CalculateIndex(string word)
    {
        Debug.Assert(!string.IsNullOrEmpty(word));
        return (word[0] - 97)*26 + (word[word.Length - 1] - 97);
    }

    public IEnumerable&lt;string&gt; SuggestWords(string input)
    {
        if (string.IsNullOrEmpty(input))
        {
            return Enumerable.Empty&lt;string&gt;();
        }
        var candidates = (cache[CalculateIndex(input)] ?? Enumerable.Empty&lt;string&gt;());
        return candidates.Where(candidate =&gt; CheckWordIsValidForInput(candidate, input));
    }

    private bool CheckWordIsValidForInput(string word, string input)
    {
        int currentPosition = 0;
        foreach (var c in word)
        {
            currentPosition = input.IndexOf(c, currentPosition);
            if (currentPosition == -1)
            {
                return false;
            }
        }
        return true;
    }
}


The responsibility of this class is to take a dictionary of words and sort it into an array of lists of words. The index of the array is determined by a simple calculation of the first and last letters of the word (CalculateIndex). Which gives us an O(1) lookup for the list of candidate words. This is the same complexity as using a dictionary would have but has smaller constant terms than using the dictionary. The overall algorithm is  O(n*m) with O(n) startup cost where n is the number of words and m is the length of the input string. The memory requirement is O(k^2) where k is the alphabet length (hard coded to 26 here).

I benchmarked this against the OP's solution and Jonbot's dictionary and found that for input 1 over 10000 iterations it's approximately twice as fast as Jobbot's and about 200 times faster than OPs solution. For words with a larger list of candidates, i.e. more common first and last letters, it ends up being only very slightly faster ~5% that the dictionary approach but still an order of magnitude faster than the OP.

Usage of the code:

 var words = File.ReadAllLines(@"C:\some\path\to\dictionary.txt");
 var autoCompleteCache = new AutocompleteCache(words);
 var results = autoCompleteCache.SuggestWords("quen"); 
 Console.WriteLine(string.Join(", ", results)); // queen


Looking for any and all comments.
To me it looks fine. Just some minor adjustments:

I think it would look even nicer if you defined constants for the magic numbers.

 const int AlphabetLength = 26;
 const int MinWordLength = 5;


In place of 97 I'd put simply an 'a'.



Instead of


currentPosition == -1



I suggest

currentPosition &lt; 0


The -1 looks like a magic number. I sometimes use a constant for it that I name IndexOutOfRange.



You use var everywhere but here :-)


int currentPosition = 0;





It might also be a good idea to move the code from the constructor into a new method like AddWords or AddWord so you can extend the dictionary later if necessary. Usually those dictionaries can learn new words.