Word Ladder
Find the length of the shortest transformation sequence from beginWord to endWord, changing one letter at a time through words in wordList.
Intuition
It is tempting to compare every word against every other word to decide which pairs are one letter apart, but that is O(n^2 L) before the BFS even starts. Instead, never build the graph at all: for the current word, try swapping in each of the 26 letters at each position, and check whether the result is in the word set. That generates exactly the neighbors that matter, on demand, in O(L 26) per word. The graph is implicit - it exists only as a rule for generating edges, computed lazily as BFS needs them.
BFS over an implicit graph — the words are nodes and a single-letter change is an edge, but the edges are generated on demand rather than stored. Removing a word from the set as it's enqueued is the visited marker, and it doubles as the deduplication.
Approach
Guard the target
If endWord is not in wordList, no sequence of legal one-letter swaps can ever land on it, so return 0 immediately.
Generate neighbors on demand
From the current word, for each position and each of the 26 letters, build the candidate word. If it is in the word set and unvisited, it is a genuine neighbor - no precomputed adjacency list needed.
BFS layer = transformation count
Track distance from beginWord (starting at 1). The first time endWord is generated, its distance is the answer, since BFS explores shortest sequences first.
Solution & live demo
Common pitfalls
Comparing every pair of words to build edges
for a in words:
for b in words:
if differs_by_one(a, b): adj[a].append(b)for i in range(len(word)):
for ch in 'abcdefghijklmnopqrstuvwxyz':That's O(N²·L) in the word count. Generating the 26·L neighbours of a word and testing set membership is O(26·L) per word, independent of how many words exist.
Not removing words when enqueuing
if cand in words:
q.append((cand, d + 1))if cand in words:
words.discard(cand)
q.append((cand, d + 1))The same word would be reached from several predecessors and enqueued repeatedly, blowing up the queue exponentially. Since BFS finds the shortest route first, later arrivals can be discarded outright.
Skipping the endWord membership check
q = deque([(beginWord, 1)])
if endWord not in words:
return 0If the target isn't in the word list no transformation sequence exists, and the BFS would exhaust the entire reachable set before returning 0. The check is immediate and states the precondition.
Edge cases
Return 0 right away, no BFS needed.
Not a valid LeetCode input, but would resolve trivially.
They are simply never generated as neighbors and never visited.
BFS queue empties without reaching endWord; return 0.