Problem overview
LadderLength(beginWord, endWord, words) returns the number of words in the shortest chain that turns beginWord into endWord. Each step changes exactly one letter, and every word you step onto must be in words. The chain counts both ends, and the method returns 0 when no chain exists. All words have the same length and use only lowercase letters.
With beginWord = "hit", endWord = "cog" and words = ["hot","dot","dog","lot","log","cog"], one shortest chain is hit -> hot -> dot -> dog -> cog. It has five words, so the answer is 5. If "cog" is missing from the list, nothing can ever step onto it, and the answer is 0.
Approach: BFS over an implicit graph
Think of every word as a node, with an edge between two words that differ in one letter. The question becomes: what is the fewest nodes on a path from beginWord to endWord? Breadth-first search answers that, because it visits nodes in order of distance. The first time it reaches a word, it has found the shortest way there.
The graph is never built explicitly. For a word of length L, every neighbor can be produced by trying all 26 letters at each of the L positions and keeping the results that exist in the word list. That is at most 26 * L candidates per word, which is cheap as long as checking "is this in the list?" is fast. A List<string> would scan every element, so the lesson copies the words into a HashSet<string> first.
Two other lessons on this problem build a pattern index (h*t style keys) or search from both ends. This one keeps the idea simplest: generate candidates and test them.
Step by step
- Build
wordSetfrom the list. TheHashSet<string>constructor accepts any collection, and lookups then takeO(1)on average. - Create the queue. A
Queue<string>hands words back first in, first out, which is what keeps the search level by level. - Create
minDist. ThisDictionary<string, int>stores the chain length for each word reached. A word that has an entry has been seen, so the dictionary doubles as the visited set and no separate set is needed. - Seed the search. Enqueue
beginWordand set its distance to1. The answer counts words, not changes, so a chain holding only the start has length 1. - Loop while the queue has words, using
queue.Count, a property with no parentheses. Dequeue the front word. - Stop at the target. If the dequeued word equals
endWord,break. Words leave the queue in order of distance, so the distance already stored forendWordis the shortest. - Try every position and every letter. A
charloop from'a'to'z'works because++moves acharto the next character code. - Build the candidate from the part before position
i, the new letter, and the part after. - Filter. Skip candidates that are not in
wordSet. Skip those already inminDist: they were reached earlier by a chain at least as short. This second check also skipsworditself, which appears whencequals the letter already at positioni. - Record and enqueue. A surviving candidate is one step further than
word, so its distance isminDist[word] + 1. Writing that when the word is queued, not when it is dequeued, guarantees each word enters the queue once. - Return the answer.
GetValueOrDefault(endWord, 0)gives the stored distance, or0if the search never reachedendWord.
The solution in C#
class Solution {
public int LadderLength(string beginWord, string endWord, List<string> words) {
HashSet<string> wordSet = new HashSet<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;
}
for (int i = 0; i < word.Length; ++i) {
for (char c = 'a'; c <= 'z'; ++c) {
string nextWord = word.Substring(0, i) + c + word.Substring(i + 1);
if (!wordSet.Contains(nextWord)) {
continue;
}
if (minDist.ContainsKey(nextWord)) {
continue;
}
minDist[nextWord] = minDist[word] + 1;
queue.Enqueue(nextWord);
}
}
}
return minDist.GetValueOrDefault(endWord, 0);
}
}C# details worth knowing
word.Substring(0, i)takes a start index and a length, so with a start of 0 it returns the firsticharacters.word.Substring(i + 1)runs to the end. For"hit"withi = 1, the two parts are"h"and"t".- Strings are immutable, so you can't assign to
word[i]. Every candidate is a brand new string. Code ported from Java often reaches forcharAtorsetCharAt; in C# the indexerword[i]only reads. - Adding a
charto a string appends that character:"h" + 'o' + "t"is"hot". The expression is evaluated left to right, so the first operand is already a string. ==on two strings compares their contents, soendWord == worddoes what you want.- Reading
minDist[endWord]for a missing key throwsKeyNotFoundException.GetValueOrDefaultreturns the fallback you give it instead. Dictionary,HashSetandQueuelive inSystem.Collections.Generic.
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 tries L positions times 26 letters, and each candidate costs O(L) to build and hash. That gives O(N * L^2 * 26) time, which is O(N * L^2) since 26 is a constant. The set, the dictionary and the queue hold at most N strings of length L, so space is O(N * L).
Edge cases and common mistakes
endWordnot in the list. The search runs until the queue empties, never records a distance forendWord, and returns0.beginWordnot in the list. That is allowed. The start never has to be inwordSet; only the words you step onto do.- Counting changes instead of words. Starting the distance at 0 gives an answer one too small.
- Marking visited too late. If you record the distance when dequeuing, the same word can be queued many times by different neighbors.
- Using the indexer on a missing key in the final return, which throws instead of returning
0.
Testing
Running the solution on small inputs gives these results.
hit -> cog, words hot dot dog lot log cog -> 5
hit -> cog, words hot dot dog lot log -> 0
hot -> dot, words dot -> 2
The last one has a start word that isn't in the list, and the answer is still 2.