NeetCode #623LC-127HardGraphsNC 150NC 250
← Back to All Problems#623 · #127 · Word Ladder(单词接龙)
📌 Problem Statement & Constraints
A transformation sequence from
beginWord to endWord changes one letter at a time, and every intermediate word must be in wordList. Return the length of the shortest sequence (counting both endpoints), or 0 if none exists. Constraints: 1 <= beginWord.length <= 10, 1 <= wordList.length <= 5000, all words have the same length and are distinct.💡 Core Algorithmic Approaches
- Model the words as nodes in an unweighted graph with an edge when two words differ in exactly one letter.
- BFS gives the shortest path length.
- Building the graph explicitly is O(n^2 * L); instead use wildcard buckets: for each word and each position, generate the pattern with
*at that position. - Two words are neighbours exactly when they share a pattern, which turns neighbour lookup into a hash-map fetch.
💻 Benchmark Python3 Implementation
class Solution:
def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
from collections import defaultdict, deque
words = set(wordList)
if endWord not in words:
return 0 # the target is not reachable
L = len(beginWord)
# wildcard pattern -> words matching it
buckets = defaultdict(list)
for w in words:
for i in range(L):
buckets[w[:i] + "*" + w[i + 1:]].append(w)
q = deque([(beginWord, 1)])
seen = {beginWord}
while q:
w, dist = q.popleft()
if w == endWord:
return dist
for i in range(L):
pattern = w[:i] + "*" + w[i + 1:]
for nxt in buckets[pattern]:
if nxt not in seen:
seen.add(nxt)
q.append((nxt, dist + 1))
buckets[pattern] = [] # clear: no need to revisit these
return 0⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n * L^2): building the buckets costs O(n * L^2) due to string slicing, and the BFS is O(n * L).
💾 Space Complexity
O(n * L) for the buckets.
⚠️ Interview Pitfalls & Follow-ups
- Comparing every pair of words for adjacency: O(n^2 * L) graph construction.
- Forgetting the
endWord not in wordscheck: the BFS would explore everything and return 0. - Counting edges instead of words: the answer counts both endpoints, so the starting distance is 1.
- Not clearing the bucket after processing: harmless but wasteful; clearing avoids redundant lookups.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.