⚡Flashcard Drill➔
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

  1. Model the words as nodes in an unweighted graph with an edge when two words differ in exactly one letter.
  2. BFS gives the shortest path length.
  3. 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.
  4. 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 words check: 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.
🎯 Drill This Card Now➔

🧩 Related Graphs Problems