Make it fast

I spent an afternoon on the Word Chain kata. The challenge is given two words of equal length (e.g. CODE and MESS) to find words that change one into the other, altering one letter at a time, so CODE MODE MODS MOSS MESS.

I got it to work, using the SCOWL dictionary. I improved my algorithm, by searching from both ends rather than just one. I split classes into smaller ones with limited responsibilities - a ChainSeeker, a Tentacle, a Route. It was better.

I then decided, uncharacteristically for me, to make it fast. So a list of used words was replaced by a hashmap. It was faster.

As I proceeded, the slowest part was finding the possible words to go next. Input CODE, output a list of MODE, NODE, COPE, CODA etc. Here's the final code I used:

public List<string> GetPossibleNextWords(string word)
{
    List<string> result = new List<string>();
    int wordhash = HashMap.MyHash(word);

    for (int i = 0; i < word.Length; i++)
    {
        string before = String.Empty, after = String.Empty;
        long hash0 = wordhash - HashMap.HashAt(word[i], i, word.Length);

        char skipc = word[i];
        for (char c = 'a'; c <= 'z'; c++)
        {
            if (c == skipc)
                continue;
            long hash = HashMap.HashAt(c, i, word.Length);
            if (KnownHash(hash + hash0))
            {
                if (before == String.Empty && after == String.Empty)
                {
                    before = i > 0 ? word.Substring(0, i) : String.Empty;
                    after = i + 1 < word.Length ? word.Substring(i + 1) : String.Empty;
                }
                result.Add(before + c + after);
            }
        }
    }
    return result;
}

It's faster, but it's worse. I'm taking advantage of understanding the hash algorithm to calculate the new hash from changing a letter. I'm keeping these strings before and after blank until I really need them, then holding them in memory on the off-chance that I need them again.

I daresay it could be made faster still. I'm sure that creating and passing List<string> objects is inefficient. But I think I've learned something, which is that I can keep making code faster, but at the expense of legibility.