Word Ladder — Solution

Problem

You are given two words and a dictionary of valid words. Starting from the first word, find the length of the shortest sequence of one-letter substitutions that transforms it into the second word, where every intermediate word (and the final word) must exist in the dictionary.

• Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
• Output: 5
• Explanation: "hit" → "hot" → "dot" → "dog" → "cog" is the shortest valid 5-word sequence

If no such sequence exists — either because endWord isn't in the dictionary or no chain of single-letter changes can reach it — return 0.

Intuition

This is a shortest-path problem disguised as a word puzzle. Each word is a node, and two nodes share an edge when they differ by exactly one letter. BFS is the right tool because it explores all words reachable in 1 step before words reachable in 2 steps, so the first time you reach endWord is guaranteed to be along the shortest path. The key efficiency trick is generating each word's neighbors on the fly — try all 26 letters at each character position — rather than pre-building the full graph, which would cost O(N²) pairwise comparisons.

Solution — BFS on Implicit Word Graph

Use level-by-level BFS from beginWord, generating neighbors by substituting each character with 'a' through 'z'. Words are marked visited by removing them from the set when first seen, so they're never re-enqueued.

1. Convert wordList to a hash set; return 0 immediately if endWord is absent.
2. Push beginWord into the queue and remove it from the set (it's already visited).
3. At each BFS level, snapshot the queue size to process exactly one layer at a time.
4. For each word in the layer, try all L × 26 single-character substitutions.
5. If a substitution matches endWord, return steps + 1.
6. If a substitution is in the word set, remove it (marking it visited) and enqueue it.

1from collections import deque
2
3class Solution:
4    def ladderLength(self, beginWord: str, endWord: str, wordList: list[str]) -> int:
5        word_set = set(wordList)
6        if endWord not in word_set:
7            return 0
8
9        queue = deque([beginWord])
10        word_set.discard(beginWord)  # removal from set acts as visited marker
11        steps = 1
12
13        while queue:
14            for _ in range(len(queue)):
15                word = queue.popleft()
16                for i in range(len(word)):
17                    for char in 'abcdefghijklmnopqrstuvwxyz':
18                        next_word = word[:i] + char + word[i + 1:]
19                        if next_word == endWord:
20                            return steps + 1
21                        if next_word in word_set:
22                            word_set.discard(next_word)
23                            queue.append(next_word)
24            steps += 1
25
26        return 0

Time: O(N × L²) — for each of N words we try 26 × L substitutions, and each hash set lookup hashes a string of length L, so O(L) per lookup.

Space: O(N × L) — the word set and BFS queue together hold at most N words of length L.

Complexity Summary

Common Mistakes

• Not checking whether endWord is in the dictionary first — if it's absent no path can exist; without this check, BFS will traverse every reachable word before returning 0, wasting all of it.
• Forgetting to mark beginWord as visited — if beginWord also appears in wordList, BFS can circle back to it; removing it from the set at the start breaks that cycle.
• Marking words visited only when dequeuing, not when enqueuing — the same word can be discovered via multiple neighbors in the same BFS layer and enqueued multiple times, inflating queue size and producing wrong step counts.
• Off-by-one on the step counter — the sequence length includes beginWord itself, so the count starts at 1; when you first discover endWord as a neighbor you return steps + 1, not steps.
• Allocating new strings in a tight loop in Java/C++ — Python's string slicing is unavoidable at O(L) per substitution, but in Java and C++ you can mutate a single character in a char[] / string and restore it after each attempt, avoiding N × L × 26 string allocations.

Related Problems

• 01-matrix — multi-source BFS where every 0-cell is a simultaneous starting point; same layer-by-layer expansion to find shortest distance
• snakes-and-ladders — BFS for minimum dice rolls on a board; each board position is a node, legal moves are edges
• evaluate-division — builds a weighted graph between variables and answers ratio queries with BFS; same idea of traversing an implicit graph
• clone-graph — BFS traversal of an unknown graph by following edges as they're discovered, rather than pre-enumerating neighbors
• number-of-islands — BFS/DFS on a grid's implicit adjacency graph; same pattern of marking cells visited by erasing them in place