What pattern does Word Ladder use?

The Pattern: BFS (Shortest Path on Unweighted Graph) The Heuristic: When searching for the shortest sequence of transformations or steps in a state space where each move has equal cost, model the problem as a graph and use BFS to explore layer by layer, guaranteeing the first time you reach the target is the shortest path.

Word Ladder — BFS

Problem

Given two words beginWord and endWord, and a list of words wordList, return the length of the shortest transformation sequence from beginWord to endWord such that only one letter can be changed at a time and each transformed word must exist in wordList. Return 0 if no such sequence exists.

1 ≤ beginWord.length ≤ 10
endWord.length == beginWord.length
1 ≤ wordList.length ≤ 5000
wordList[i].length == beginWord.length
beginWord, endWord, and wordList[i] consist of lowercase English letters
beginWord != endWord

Example

Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]

Output: 5

The shortest transformation sequence is "hit" -> "hot" -> "dot" -> "dog" -> "cog". The algorithm starts from "hit" and explores all words one letter away that exist in the wordList. It uses a BFS to find the shortest path, layer by layer. The critical moment is when "cog" is reached at the fifth step, confirming the shortest transformation length is 5.

Approach

Straightforward Solution

A brute-force approach would try all possible sequences of transformations, which is exponential in the worst case and infeasible for large word lists.

Core Observation

The problem asks for the shortest sequence of transformations where each step changes exactly one letter and results in a valid word. This naturally models a graph where each word is a node and edges connect words differing by one letter.

Path to Optimal

Preview

Recognizing the problem as a shortest path in an unweighted graph leads to BFS as the optimal approach. However, building the graph explicitly by comparing every pair of words is O(n^2 * word_length), which is expensive…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Preprocess the word list to create a mapping from generic intermediate patterns (with one letter replaced by '*') to all words matching that pattern. Then perform BFS starting from beginWord, exploring neighbors via these patterns…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(M * N) where N is the number of words and M is the length of each word

Preprocessing the word list to build the pattern-to-word mapping takes O(M * N). BFS explores each word at most once, and for each word, it checks M patterns, leading to O(M * N) total operations.

Space

O(M * N)

The adjacency mapping stores up to M patterns for each of the N words, resulting in O(M * N) auxiliary space. The BFS queue and visited set also use O(N) space.

Solution

Python

1import collections
2
3class Solution:
  def ladderLength(self, beginWord: str, endWord: str, wordList: list[str]) -> int:
      if endWord not in wordList:
          return 0
7
      nei = collections.defaultdict(list)
      wordList.append(beginWord)
      for word in wordList:
          for j in range(len(word)):
              pattern = word[:j] + "*" + word[j + 1:]
              nei[pattern].append(word)
      
      visit = set([beginWord])
      q = collections.deque([beginWord])
      res = 1
      while q:
          for i in range(len(q)):
              word = q.popleft()
              if word == endWord:
                  return res
              for j in range(len(word)):
                  pattern = word[:j] + "*" + word[j + 1:]
                  for neiWord in nei[pattern]:
                      if neiWord not in visit:
                          visit.add(neiWord)
                          q.append(neiWord)
          res += 1
      return 0

Step-by-Step Solution

1

Build Pattern-to-Words Mapping to Represent Graph Edges

8nei = collections.defaultdict(list)
9wordList.append(beginWord)
10for word in wordList:
11    for j in range(len(word)):
12        pattern = word[:j] + "*" + word[j + 1:]
13        nei[pattern].append(word)

Objective

To create a mapping from generic intermediate patterns to all words matching that pattern, enabling efficient neighbor lookup.

Key Insight

Replacing each letter in a word with '*' generates patterns that group words differing by exactly one letter. This transforms the problem of finding neighbors from O(N^2) pairwise comparisons to O(M*N) preprocessing. The mapping acts as an implicit adjacency list, allowing BFS to quickly find all valid next words by pattern lookup.

Interview Quick-Check

Core Logic

The pattern mapping groups words by their one-letter-different forms, enabling O(1) average-time neighbor retrieval during BFS.

Common Pitfalls & Bugs

Forgetting to include the beginWord in the word list before building the mapping can cause missing neighbors and incorrect results.

State & Boundaries

Each pattern replaces exactly one character with '*', ensuring all neighbors differ by one letter.

2

Perform BFS to Explore Transformation Sequences Layer by Layer

To traverse the implicit graph using BFS, tracking visited words and counting transformation steps until the endWord is found.

1 more step with full analysis available on Pro.

Line Analysis

This solution has 7 Critical lines interviewers watch for.

Line 5 Critical

if endWord not in wordList:

Check if endWord is in wordList to determine if transformation is possible.

If endWord is not in wordList, no valid transformation sequence can reach it, so returning 0 immediately avoids unnecessary computation.

Line 9 Critical

wordList.append(beginWord)

Add beginWord to wordList to include it in the pattern mapping.

Including beginWord ensures that neighbors of the start word are correctly identified, preventing missing valid transformation paths.

Line 13 Critical

nei[pattern].append(word)

Append the current word to the list of words matching the pattern.

Building the adjacency list by pattern groups allows BFS to find all neighbors of a word by looking up patterns rather than comparing words pairwise.

Full line-by-line criticality + rationale for all 24 lines available on Pro.

Test Your Understanding

Why does BFS guarantee the shortest transformation sequence in this problem?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Word Ladder from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Word Ladder drill

or drill a free problem

1	`import collections`
2
3	`class Solution:`
4	`def ladderLength(self, beginWord: str, endWord: str, wordList: list[str]) -> int:`
5	`if endWord not in wordList:`
6	`return 0`
7
8	`nei = collections.defaultdict(list)`
9	`wordList.append(beginWord)`
10	`for word in wordList:`
11	`for j in range(len(word)):`
12	`pattern = word[:j] + "*" + word[j + 1:]`
13	`nei[pattern].append(word)`
14
15	`visit = set([beginWord])`
16	`q = collections.deque([beginWord])`
17	`res = 1`
18	`while q:`
19	`for i in range(len(q)):`
20	`word = q.popleft()`
21	`if word == endWord:`
22	`return res`
23	`for j in range(len(word)):`
24	`pattern = word[:j] + "*" + word[j + 1:]`
25	`for neiWord in nei[pattern]:`
26	`if neiWord not in visit:`
27	`visit.add(neiWord)`
28	`q.append(neiWord)`
29	`res += 1`
30	`return 0`

8	`nei = collections.defaultdict(list)`
9	`wordList.append(beginWord)`
10	`for word in wordList:`
11	`for j in range(len(word)):`
12	`pattern = word[:j] + "*" + word[j + 1:]`
13	`nei[pattern].append(word)`