Start learning free

LESSON 344 OF 347 · GRAPHS

Word Ladder in C#: Bidirectional BFS, Level by Level

Practice O(N * L²) Read the full explanation

Given two words (beginWord and endWord), and a dictionary's word list, find the length of shortest transformation sequence from beginWord to endWord, such that:

Only one letter can be changed at a time.
Each transformed word must exist in the word list.

Note:

Return 0 if there is no such transformation sequence.
All words have the same length.
All words contain only lowercase alphabetic characters.
You may assume no duplicates in the word list.
You may assume beginWord and endWord are non-empty and are not the same.

Example 1:

Input:
beginWord = "hit",
endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"]

Output: 5

Explanation: As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.

Example 2:

Input:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]

Output: 0

Explanation: The endWord "cog" is not in wordList, therefore no possible transformation.

STEP 1 OF 34

Guided

Ctrl + Enter to check

C# · GRAPHS

Word Ladder in C#, explained

Problem overview

LadderLength(beginWord, endWord, words) returns the number of words in the shortest chain from beginWord to endWord. Each step changes one letter, every word stepped onto must be in words, and the count includes both ends. When no chain exists, the answer is 0. All words have the same length and use lowercase letters only.

For hit to cog with words = ["hot","dot","dog","lot","log","cog"], the chain hit -> hot -> dot -> dog -> cog has 5 words, so the answer is 5.

Approach: search from both ends

A plain breadth-first search from beginWord explores every word within distance d before it reaches a word at distance d + 1. When each word has many neighbors, that frontier grows quickly. Searching from both ends at once keeps both frontiers small: each side only needs to go about half the distance, and the two searches meet in the middle.

Neighbors are found with a pattern index, as in the previous version of this problem: replace one letter with *, and words that share a pattern differ in exactly one letter.

Two details make the meeting logic correct:

Each side expands a whole level at a time. If the searches advanced one word at a time, they could meet through a longer chain while a shorter one was still waiting in a queue.
Each side keeps its own distance dictionary. When one side is about to visit a word that the other side has already reached, the chain length is the sum of the two distances.

Step by step

Handle the impossible case first. If words doesn't contain endWord, return 0. The second search starts from endWord, and no chain can end on a word that isn't in the list.
Write GetStarWord(word, i), which returns word with the letter at index i replaced by *, built from two Substring calls.
Write BuildGraph(words). It loops over every word and every position, and adds the word to the list stored under its pattern, creating that list when the key is new. It returns the finished dictionary.
Create the two searches' state in LadderLength: beginQueue and endQueue, plus beginMinDist and endMinDist. Each dictionary maps a word to the length of the chain from that side's start (counting both ends), and its keys are also that side's visited set.
Seed both sides. Enqueue beginWord and endWord into their own queues, and set each one's distance to 1.
Write ProcessLevel. It takes the graph, the queue of the side being expanded, that side's distances, and the other side's distances. It first stores queue.Count in levelSize, because the words enqueued during this call belong to the next level.
Loop exactly levelSize times. Comparing the counter with levelSize and not with queue.Count is what stops the call from expanding the words it just added.
Dequeue a word, then for each position compute its pattern and get the list of words stored under it. graph.TryGetValue(starWord, out var nb) ? nb : new List<string>() picks the list when the key exists and an empty one otherwise.
Check for a meeting. If otherMinDist contains nextWord, return minDist[word] + otherMinDist[nextWord]. The first term counts the words from this side's start up to word, the second counts the words from nextWord to the other end, and the two are different words, so none is counted twice.
Otherwise visit it. If minDist has no entry for nextWord, set it to minDist[word] + 1 and enqueue it.
Return 0 after the loops. It means "this level did not meet the other search". A real chain has at least two words, so 0 can't be mistaken for an answer.
Drive the loop in LadderLength. While both queues are non-empty, expand the side with fewer words, which is the cheaper one to grow. Store the return value in result and return it as soon as it is positive.
Return 0 after the loop. If one side ran out of words, the searches can never meet.

The solution in C#

class Solution {
    string GetStarWord(string word, int i) {
        return word.Substring(0, i) + "*" + word.Substring(i + 1);
    }

    Dictionary<string, List<string>> BuildGraph(List<string> words) {
        var graph = new Dictionary<string, List<string>>();
        foreach (string word in words) {
            for (int i = 0; i < word.Length; ++i) {
                string starWord = GetStarWord(word, i);
                if (!graph.ContainsKey(starWord)) {
                    graph[starWord] = new List<string>();
                }
                graph[starWord].Add(word);
            }
        }
        return graph;
    }

    int ProcessLevel(Dictionary<string, List<string>> graph, Queue<string> queue, Dictionary<string, int> minDist, Dictionary<string, int> otherMinDist) {
        int levelSize = queue.Count;
        for (int k = 0; k < levelSize; ++k) {
            string word = queue.Dequeue();
            for (int i = 0; i < word.Length; ++i) {
                string starWord = GetStarWord(word, i);
                List<string> neighbors = graph.TryGetValue(starWord, out var nb) ? nb : new List<string>();
                foreach (string nextWord in neighbors) {
                    if (otherMinDist.ContainsKey(nextWord)) {
                        return minDist[word] + otherMinDist[nextWord];
                    }
                    if (!minDist.ContainsKey(nextWord)) {
                        minDist[nextWord] = minDist[word] + 1;
                        queue.Enqueue(nextWord);
                    }
                }
            }
        }
        return 0;
    }

    public int LadderLength(string beginWord, string endWord, List<string> words) {
        if (!words.Contains(endWord)) {
            return 0;
        }
        var graph = BuildGraph(words);
        var beginQueue = new Queue<string>();
        var endQueue = new Queue<string>();
        var beginMinDist = new Dictionary<string, int>();
        var endMinDist = new Dictionary<string, int>();
        beginQueue.Enqueue(beginWord);
        endQueue.Enqueue(endWord);
        beginMinDist[beginWord] = 1;
        endMinDist[endWord] = 1;
        int result = 0;
        while (beginQueue.Count > 0 && endQueue.Count > 0) {
            if (beginQueue.Count <= endQueue.Count) {
                result = ProcessLevel(graph, beginQueue, beginMinDist, endMinDist);
            } else {
                result = ProcessLevel(graph, endQueue, endMinDist, beginMinDist);
            }
            if (result > 0) {
                return result;
            }
        }
        return 0;
    }
}

Why the tie-break uses `<=`

When both queues have the same size, the code expands the begin side. This matters in the very first pass, where each queue holds one word. beginWord is allowed to be missing from words, and then it has no entry in the graph for the end side to step onto. Only the begin side's first expansion can link it to the other words. Take beginWord = "hot", endWord = "dot" and words = ["dot"]: with < in place of <=, the end side goes first, finds nothing new, and the method returns 0 instead of 2. With <= the answer is 2.

Why returning at the first meeting is safe

Both searches grow one full level per call, so after each call every word within a certain distance of that side has been recorded. If a shorter chain existed, the two searches would have met in an earlier call. The first meeting therefore gives the shortest length.

C# details worth knowing

Queue and Dictionary are reference types, so ProcessLevel changes the caller's queue and dictionaries directly. It doesn't need to return them.
out var nb declares the variable inside the call to TryGetValue. It is in scope for the rest of the statement and, in a declaration like this one, for the statement's enclosing block.
The helper methods have no access modifier, so they are private to the class. That's all LadderLength needs.
words.Contains(endWord) on a List<string> is a linear scan. That is fine for one check at the start.

Complexity

Let N be the number of words and L their length. Building the pattern index takes O(N * L^2) time and space, as each of the N * L patterns is a string of length L. The search visits each word at most once per side, and for each visit it builds L patterns and scans buckets of at most 26 words, so the worst case is also O(N * L^2). The benefit of searching from both ends shows up in practice: each frontier covers about half the distance, so far fewer words are touched than with one search covering the whole distance. The worst case does not improve, for example when the answer is 0 and everything is explored.

Edge cases and common mistakes

endWord missing from the list: the first line returns 0.
beginWord missing from the list: allowed, and the reason the begin side goes first on a tie.
Expanding one word at a time instead of a whole level can produce a chain that is not the shortest.
Looping to queue.Count inside ProcessLevel: the bound changes as words are enqueued, so the call would expand more than one level.
Adding the two distances wrongly: each side counts its own start word, and word and nextWord are different, so the plain sum is right. Subtracting 1 would be a mistake.
One side runs dry: the loop condition requires both queues to be non-empty, because an empty side can no longer meet the other.

Testing

hit -> cog, words hot dot dog lot log cog   ->  5
hit -> cog, words hot dot dog lot log       ->  0
hot -> dot, words dot                       ->  2

Keep going with C#About 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free