Word ladder

Shortest chain from one word to another, changing one letter per step, always through words in the list. BFS over a graph of words.

The idea

Picture every word as a node, with an edge between two words that differ in exactly one letter. The shortest transformation sequence is then just the shortest path in that graph, found with ordinary layer-by-layer BFS: each layer is one more word in the chain.

Code

public static int LadderLength(string begin, string end, HashSet<string> wordList) {
    var queue = new Queue<string>();
    queue.Enqueue(begin);
    var seen = new HashSet<string> { begin };
    int steps = 1;
    while (queue.Count > 0) {
        int size = queue.Count;
        for (int i = 0; i < size; i++) {
            string word = queue.Dequeue();
            if (word == end) return steps;
            foreach (string next in Neighbours(word, wordList))
                if (seen.Add(next)) queue.Enqueue(next);
        }
        steps++;
    }
    return 0; // end is unreachable
}

Tips

• Build the "changes one letter" neighbours by trying every position and every other letter, keeping only results that are in the word list.
• Precomputing a word -> neighbours map once is far faster than rescanning the whole list for every word during the search.

In the .NET library

Interview answers often quote O(N × L²) time: N words, each compared or mutated in roughly L positions times L alphabet tries (26) times length-L string work; a two-ended BFS from both begin and end halves the frontier in practice.