Problem overview
LadderLength(beginWord, endWord, words) returns how many words are on the shortest chain from beginWord to endWord, where each step changes one letter and each word stepped onto is in words. The count includes both ends. If no chain exists, it returns 0. All words have the same length and contain lowercase letters only.
For beginWord = "hit", endWord = "cog" and words = ["hot","dot","dog","lot","log","cog"], the chain hit -> hot -> dot -> dog -> cog has 5 words, so the answer is 5. If "cog" is not in the list, the answer is 0.
Approach: index words by wildcard pattern
Breadth-first search finds the shortest chain because it reaches words in order of distance. The question is how to find a word's neighbors. Trying 26 letters at every position works, but most candidates are not words at all.
This lesson avoids that waste with a precomputed index. Replace one letter of a word with * and you get a pattern: hot gives *ot, h*t and ho*. Two words differ in exactly one letter when they share a pattern. For example, hot and dot both produce *ot. So a dictionary from pattern to the list of words with that pattern is a ready-made neighbor lookup.
The search then asks, for each dequeued word, "which words share each of my patterns?" instead of "which of my 26 * L candidates exist?". The shortest-path logic is the same as in the plain BFS version of this problem; only the neighbor finding changes.
Step by step
- Create
graph, aDictionary<string, List<string>>from pattern to the words that match it. - Loop over the words and over every position
iof each word. Each word contributes one pattern per position. - Write
GetStarWord(word, i). It returns the part ofwordbeforei, then"*", then the part afteri. TwoSubstringcalls build it:Substring(0, i)takes the firsticharacters (its second argument is a length, not an end index), andSubstring(i + 1)runs to the end. - Fill the index. Compute
starWordfor each word and position. Ifgraphhas no key for it yet, store a new empty list; then add the word to that list. The target-typednew()works because the compiler knows the dictionary's value type isList<string>. - Set up the BFS after both loops: a
Queue<string>, and aDictionary<string, int>namedminDistthat maps each reached word to its chain length (counting both ends). Having an entry means "already visited". - Seed it. Enqueue
beginWordand setminDist[beginWord] = 1. A chain containing only the start has one word. - Loop while
queue.Count > 0. Dequeue a word. If it equalsendWord,break: words come out of the queue in order of distance, so the stored distance is the shortest. - For each position of the dequeued word, compute its pattern again with
GetStarWord. Every word stored under that pattern differs from it at that position only. - Visit the neighbors. Loop over
graph.GetValueOrDefault(starWord, new()). The empty default means a pattern that isn't in the index gives a loop that runs zero times, instead of throwingKeyNotFoundException. - Skip visited words. If
minDisthas no entry fornextWord, set its distance tominDist[word] + 1and enqueue it. The word itself matches its own pattern, but it already has an entry, so it is skipped. - Return
minDist.GetValueOrDefault(endWord, 0).
The solution in C#
class Solution {
public string GetStarWord(string word, int i) {
return word.Substring(0, i) + "*" + word.Substring(i + 1);
}
public int LadderLength(string beginWord, string endWord, List<string> words) {
Dictionary<string, List<string>> 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();
}
graph[starWord].Add(word);
}
}
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) {
string starWord = GetStarWord(word, i);
foreach (string nextWord in graph.GetValueOrDefault(starWord, new())) {
if (!minDist.ContainsKey(nextWord)) {
minDist[nextWord] = minDist[word] + 1;
queue.Enqueue(nextWord);
}
}
}
}
return minDist.GetValueOrDefault(endWord, 0);
}
}C# details worth knowing
- The variable
starWordis declared in two different loop bodies. That is fine because each loop body is its own scope. The loop variablewordin the firstforeachis also fine next to the laterstring word = queue.Dequeue();, since the first one's scope has ended by then. graph[starWord] = new();is the target-typednewexpression, available since C# 9. Writingnew List<string>()means the same thing.- The second argument of
GetValueOrDefaultis evaluated every time the call runs, so the loop allocates a small empty list per pattern lookup. That is harmless here. - Strings are immutable.
GetStarWordbuilds new strings; it never changesword.
Complexity
Let N be the number of words and L their length. Building the index creates N * L patterns, each costing O(L) to build and hash, so that takes O(N * L^2). The index stores N * L patterns of length L, so space is O(N * L^2).
In the search, each word is dequeued once and looks up L patterns. A bucket holds words that differ only at one position, and a list without duplicates can have at most 26 of those, so scanning a bucket is a constant amount of work. The search therefore costs O(N * L^2) as well, mostly for building the patterns. Compared with trying 26 letters per position, the work per step is smaller in practice, because only real neighbors are looked at; the cost is the extra memory for the index.
Edge cases and common mistakes
- Missing pattern. A word that isn't in
words, such asbeginWord, may produce patterns that were never stored. UseGetValueOrDefault(orTryGetValue), not the indexer. beginWordnot in the list. It is not in the index either, but its patterns still find the words it connects to. The start doesn't have to be a list member.endWordnot in the list. It never gets a distance, so the final line returns0.- Forgetting that a word shares its own pattern. Without the visited check, the BFS would enqueue each word again from its own bucket.
- Starting the distance at 0. The answer counts words, so the start is 1.
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
The last case has a start word that is not in the list; the answer is 2 because hot and dot share the pattern *ot.