Start learning free

LESSON 341 OF 347 · GRAPHS

Word Ladder in C#: Shortest Transformation with BFS

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 16

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 sequence that starts at beginWord and ends at endWord, where each step changes exactly one letter and every word after the first must be in words. If no such sequence exists, it returns 0. All words have the same length and contain only lowercase letters, and the two end words differ.

For "hit" to "cog" with ["hot","dot","dog","lot","log","cog"], one shortest sequence is hit, hot, dot, dog, cog. It has five words, so the answer is 5. The answer counts words, not changes. If "cog" is missing from the list, no sequence can end there, and the answer is 0.

Approach: treat words as vertices of a graph

Imagine a graph where each word is a vertex and two words are joined by an edge when they differ in exactly one position. A transformation sequence is then a path, and the shortest sequence is the shortest path from beginWord. Every edge counts the same, so breadth-first search (BFS) finds it. BFS explores all words one change away, then all words two changes away, and so on, which means the first time a word is reached it is reached by a shortest sequence.

The graph is never built explicitly. Whenever a word comes off the queue, the code scans the whole word list and picks out the words that differ from it in exactly one letter.

A dictionary called minDist maps each reached word to the length of the shortest sequence that ends with it. It has two jobs: it stores the answers, and a word that has an entry counts as visited, so no separate set is needed. The start word has length 1, since a sequence of only that word has one word in it.

Step by step

Create a Queue<string> named queue for the BFS.
Create minDist, a Dictionary<string, int>.
Enqueue beginWord and set minDist[beginWord] = 1.
Loop while queue.Count > 0.
Dequeue the front word into word.
If word equals endWord, stop with break. Its distance is already stored, and BFS guarantees it is the smallest.
Otherwise loop over every nextWord in the list.
Skip it unless NumOfChanges(word, nextWord) is exactly 1. A count of 0 means the same word, and 2 or more means too many changes.
Skip it if minDist already contains it. A word reached earlier was reached by a sequence that is at least as short.
Otherwise store minDist[word] + 1 for it and enqueue it. Storing the distance at enqueue time prevents a word from entering the queue twice.
After the loop, return the stored distance of endWord, or 0 if it was never reached.
Write the helper NumOfChanges(first, second). Start a counter differences at 0.
Loop over the indices of first, and add 1 whenever first[i] differs from second[i]. C# won't add a bool to an int, so the code uses the ternary operator cond ? 1 : 0.
Return differences.

The solution in C#

class Solution {
    public int NumOfChanges(string first, string second) {
        int differences = 0;
        for (int i = 0; i < first.Length; ++i) {
            differences += (first[i] != second[i]) ? 1 : 0;
        }
        return differences;
    }

    public int LadderLength(string beginWord, string endWord, List<string> words) {
        Queue<string> queue = new Queue<string>();
        Dictionary<string, int> minDist = new Dictionary<string, int>();
        queue.Enqueue(beginWord);
        minDist[beginWord] = 1;
        while (queue.Count > 0) {
            string word = queue.Dequeue();
            if (endWord == word) {
                break;
            }
            foreach (string nextWord in words) {
                if (NumOfChanges(word, nextWord) != 1) {
                    continue;
                }
                if (minDist.ContainsKey(nextWord)) {
                    continue;
                }
                minDist[nextWord] = minDist[word] + 1;
                queue.Enqueue(nextWord);
            }
        }
        return minDist.GetValueOrDefault(endWord, 0);
    }
}

Trace the first example. The queue holds hit at length 1. The words that differ from hit by one letter are only hot, so it gets length 2. From hot, the list has dot and lot, both at length 3. From dot comes dog (length 4), and from lot comes log (length 4). Dequeuing dog reaches cog at length 5. When cog is dequeued, the loop breaks, and the method returns 5.

Some C# details:

String comparison. == on two string values compares their contents, so endWord == word is a correct equality test. Indexing a string gives a char, and first[i] != second[i] compares two characters.
Dictionary lookups. Assigning with minDist[key] = value adds the key if it is missing and replaces the value if it exists. Reading with minDist[key] on a missing key throws KeyNotFoundException. The code only reads minDist[word] for a word that was put in the queue, which always has an entry.
GetValueOrDefault(endWord, 0) returns the stored value, or 0 if the key is absent. It handles the "no sequence" case without a separate ContainsKey check.
ContainsKey tests for a key without reading its value, and runs in constant time on average.
Count and Length. Both are properties, so neither takes parentheses. queue.Count is the number of items in the queue, and first.Length is the number of characters in a string.

Complexity

Let N be the number of words and L their length. Each word is enqueued at most once. For each dequeued word, the code scans all N words and compares up to L letters for each, so the time is O(N * N * L). That's fine for a few thousand words. Faster solutions avoid the full scan by grouping words by wildcard patterns such as h*t, and other lessons on this problem explore those ideas.

Space: O(N) for the queue and the dictionary, with each key being a word of length L.

Edge cases and common mistakes

endWord missing from the list. It can never be added to minDist, so the answer is 0. The second example shows this.
Counting changes instead of words. One change from hit to hot makes a sequence of two words. That is why the start is 1, not 0.
beginWord inside the list. It is already in minDist, so the visited check skips it and it can't be queued again.
Accepting zero changes. Allowing a difference of 0 would let a word lead to itself. The check must be exactly 1, not "at most 1".
Marking on dequeue. If the distance is stored only when a word is taken from the queue, the same word can be queued several times by different parents.
Reading a missing key. Returning minDist[endWord] directly throws KeyNotFoundException when the end word was never reached.

Testing

"hit" to "cog" with ["hot","dot","dog","lot","log","cog"] gives 5.
The same words without "cog" give 0.
"hit" to "hot" with ["hot"] gives 2.
"a" to "c" with ["a","b","c"] gives 2.
"hot" to "dog" with ["hot","dog"] gives 0, since the words are two changes apart and nothing in the list bridges them.

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