Word Ladder

Q: 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.

Hard 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

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. The key insight is to use an intermediate pattern representation (e.g., replacing one letter with '*') to group words that differ by one letter, enabling O(n * word_length) preprocessing to build adjacency lists.

Optimal Approach

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. Track visited words to avoid cycles. The BFS layer count corresponds to the transformation sequence length. Return the layer count when endWord is reached, or 0 if unreachable.

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.

Pattern Spotlight

BFS (Shortest Path on Unweighted Graph)

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.

Solution

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

1import java.util.*;
2
3public class Solution {
  public int ladderLength(String beginWord, String endWord, List<String> wordList) {
      if (!wordList.contains(endWord)) {
          return 0;
      }
8
      Map<String, List<String>> nei = new HashMap<>();
      List<String> extendedWordList = new ArrayList<>(wordList);
      extendedWordList.add(beginWord);
12
      for (String word : extendedWordList) {
          for (int j = 0; j < word.length(); j++) {
              String pattern = word.substring(0, j) + "*" + word.substring(j + 1);
              nei.computeIfAbsent(pattern, k -> new ArrayList<>()).add(word);
          }
      }
19
      Set<String> visit = new HashSet<>();
      visit.add(beginWord);
      Deque<String> q = new ArrayDeque<>();
      q.add(beginWord);
      int res = 1;
25
      while (!q.isEmpty()) {
          int size = q.size();
          for (int i = 0; i < size; i++) {
              String word = q.poll();
              if (word.equals(endWord)) {
                  return res;
              }
              for (int j = 0; j < word.length(); j++) {
                  String pattern = word.substring(0, j) + "*" + word.substring(j + 1);
                  List<String> neighbors = nei.getOrDefault(pattern, Collections.emptyList());
                  for (String neiWord : neighbors) {
                      if (!visit.contains(neiWord)) {
                          visit.add(neiWord);
                          q.add(neiWord);
                      }
                  }
              }
          }
          res++;
      }
      return 0;
  }
48}

1#include <string>
2#include <vector>
3#include <unordered_map>
4#include <unordered_set>
5#include <queue>
6
7using namespace std;
8
9class Solution {
10public:
  int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
      unordered_set<string> wordSet(wordList.begin(), wordList.end());
      if (wordSet.find(endWord) == wordSet.end()) {
          return 0;
      }
16
      unordered_map<string, vector<string>> nei;
      vector<string> extendedWordList = wordList;
      extendedWordList.push_back(beginWord);
20
      for (const string& word : extendedWordList) {
          for (int j = 0; j < (int)word.size(); ++j) {
              string pattern = word.substr(0, j) + "*" + word.substr(j + 1);
              nei[pattern].push_back(word);
          }
      }
27
      unordered_set<string> visit;
      visit.insert(beginWord);
      queue<string> q;
      q.push(beginWord);
      int res = 1;
33
      while (!q.empty()) {
          int size = (int)q.size();
          for (int i = 0; i < size; ++i) {
              string word = q.front();
              q.pop();
              if (word == endWord) {
                  return res;
              }
              for (int j = 0; j < (int)word.size(); ++j) {
                  string pattern = word.substr(0, j) + "*" + word.substr(j + 1);
                  for (const string& neiWord : nei[pattern]) {
                      if (visit.find(neiWord) == visit.end()) {
                          visit.insert(neiWord);
                          q.push(neiWord);
                      }
                  }
              }
          }
          ++res;
      }
      return 0;
  }
56};

1var ladderLength = function(beginWord, endWord, wordList) {
  if (!wordList.includes(endWord)) {
      return 0;
  }
5
  const nei = new Map();
  const extendedWordList = wordList.slice();
  extendedWordList.push(beginWord);
9
  for (const word of extendedWordList) {
      for (let j = 0; j < word.length; j++) {
          const pattern = word.slice(0, j) + '*' + word.slice(j + 1);
          if (!nei.has(pattern)) {
              nei.set(pattern, []);
          }
          nei.get(pattern).push(word);
      }
  }
19
  const visit = new Set([beginWord]);
  const q = [beginWord];
  let front = 0;
  let res = 1;
24
  while (front < q.length) {
      const size = q.length - front;
      for (let i = 0; i < size; i++) {
          const word = q[front++];
          if (word === endWord) {
              return res;
          }
          for (let j = 0; j < word.length; j++) {
              const pattern = word.slice(0, j) + '*' + word.slice(j + 1);
              const neighbors = nei.get(pattern) || [];
              for (const neiWord of neighbors) {
                  if (!visit.has(neiWord)) {
                      visit.add(neiWord);
                      q.push(neiWord);
                  }
              }
          }
      }
      res++;
  }
  return 0;
46};

Step-by-Step Solution

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.

Perform BFS to Explore Transformation Sequences Layer by Layer

15visit = set([beginWord])
16q = collections.deque([beginWord])
17res = 1
18while 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
30return 0

Objective

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

Key Insight

BFS guarantees the shortest path in an unweighted graph by exploring all nodes at the current depth before moving deeper. Using the pattern mapping, neighbors are found efficiently. The visited set prevents revisiting words, avoiding cycles and infinite loops. Incrementing the step count after processing each BFS layer corresponds to the transformation sequence length.

Interview Quick-Check

Core Logic

BFS explores all words reachable in k transformations before exploring those reachable in k+1, ensuring the first time endWord is found is the shortest path.

State & Boundaries

The loop processes all nodes in the current BFS layer before incrementing the transformation count.

Common Pitfalls & Bugs

Failing to mark words as visited immediately upon enqueueing can cause duplicate processing and incorrect shortest path calculation.

Complexity

Each word is enqueued at most once, bounding BFS runtime to O(N), where N is the number of words.

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.

Line 21 Critical

if word == endWord:

Check if the current word is the target endWord.

Finding endWord signals the shortest transformation sequence has been found, allowing immediate return.

Line 22 Critical

return res

Return the current transformation length upon reaching endWord.

Because BFS explores shortest paths first, this return value is guaranteed to be minimal.

Line 26 Critical

if neiWord not in visit:

Check if the neighbor word has not been visited.

Avoiding revisits prevents cycles and redundant processing, ensuring BFS correctness and efficiency.

Line 27 Critical

visit.add(neiWord)

Mark the neighbor word as visited.

Marking upon enqueueing prevents multiple insertions of the same word into the queue, maintaining BFS efficiency and correctness.

Line 6 Core

return 0

Return 0 when endWord is not in wordList.

This early return handles an edge case efficiently, preventing the algorithm from running on impossible inputs.

Line 8 Core

nei = collections.defaultdict(list)

Initialize a default dictionary to map patterns to words.

This data structure enables grouping words by their generic intermediate patterns, which is essential for efficient neighbor lookup during BFS.

Line 12 Core

pattern = word[:j] + "*" + word[j + 1:]

Create a generic pattern by replacing one character with '*'.

This pattern acts as a key to group words that differ by exactly one letter at this position, enabling efficient adjacency representation.

Line 15 Core

visit = set([beginWord])

Initialize a set to track visited words, starting with beginWord.

Tracking visited words prevents revisiting and cycles during BFS, ensuring correctness and efficiency.

Line 16 Core

q = collections.deque([beginWord])

Initialize a queue for BFS starting with beginWord.

The queue manages the BFS frontier, enabling layer-by-layer exploration of transformation sequences.

Line 20 Core

word = q.popleft()

Dequeue the next word to process.

FIFO order guarantees layer-by-layer traversal, essential for BFS correctness.

Line 24 Core

pattern = word[:j] + "*" + word[j + 1:]

Create a generic pattern by replacing one character with '*'.

This pattern is used to find all adjacent words in the graph efficiently.

Line 25 Core

for neiWord in nei[pattern]:

Iterate over all words matching the current pattern.

These words are all one letter different from the current word and represent valid next steps in the transformation sequence.

Line 28 Core

q.append(neiWord)

Enqueue the neighbor word for future BFS processing.

Adding neighbors to the queue expands the BFS frontier, enabling exploration of all reachable words.

Line 29 Core

res += 1

Increment the transformation sequence length after processing the current BFS layer.

Incrementing after each layer corresponds to moving one step deeper in the transformation sequence, accurately tracking path length.

Line 30 Core

return 0

Return 0 if no transformation sequence leads to endWord.

If BFS completes without finding endWord, no valid sequence exists, so returning 0 correctly signals failure.

Line 18 Core

while q:

Begin BFS loop to process words layer by layer.

The loop continues until all reachable words are explored or the endWord is found.

Line 19 Core

for i in range(len(q)):

Iterate over all words in the current BFS layer.

Processing all nodes at the current depth ensures BFS explores shortest paths first.

Line 23 Core

for j in range(len(word)):

Iterate over each character position in the current word.

Generating patterns for the current word allows lookup of all neighbors differing by one letter.

Line 11 Standard

for j in range(len(word)):

Iterate over each character position in the current word.

Replacing each character with '*' generates all possible generic patterns representing one-letter differences.

Line 17 Standard

res = 1

Initialize the transformation sequence length counter to 1.

Starting at 1 accounts for the beginWord itself as the first step in the sequence.

Line 10 Standard

for word in wordList:

Iterate over each word in the augmented wordList.

Processing every word is necessary to build the complete pattern-to-words mapping for the entire graph.

Test Your Understanding

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

Because BFS explores all nodes at the current depth before moving to the next, the first time the endWord is reached corresponds to the shortest path length, ensuring minimal transformations.

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`

1	`import java.util.*;`
2
3	`public class Solution {`
4	`public int ladderLength(String beginWord, String endWord, List<String> wordList) {`
5	`if (!wordList.contains(endWord)) {`
6	`return 0;`
7	`}`
8
9	`Map<String, List<String>> nei = new HashMap<>();`
10	`List<String> extendedWordList = new ArrayList<>(wordList);`
11	`extendedWordList.add(beginWord);`
12
13	`for (String word : extendedWordList) {`
14	`for (int j = 0; j < word.length(); j++) {`
15	`String pattern = word.substring(0, j) + "*" + word.substring(j + 1);`
16	`nei.computeIfAbsent(pattern, k -> new ArrayList<>()).add(word);`
17	`}`
18	`}`
19
20	`Set<String> visit = new HashSet<>();`
21	`visit.add(beginWord);`
22	`Deque<String> q = new ArrayDeque<>();`
23	`q.add(beginWord);`
24	`int res = 1;`
25
26	`while (!q.isEmpty()) {`
27	`int size = q.size();`
28	`for (int i = 0; i < size; i++) {`
29	`String word = q.poll();`
30	`if (word.equals(endWord)) {`
31	`return res;`
32	`}`
33	`for (int j = 0; j < word.length(); j++) {`
34	`String pattern = word.substring(0, j) + "*" + word.substring(j + 1);`
35	`List<String> neighbors = nei.getOrDefault(pattern, Collections.emptyList());`
36	`for (String neiWord : neighbors) {`
37	`if (!visit.contains(neiWord)) {`
38	`visit.add(neiWord);`
39	`q.add(neiWord);`
40	`}`
41	`}`
42	`}`
43	`}`
44	`res++;`
45	`}`
46	`return 0;`
47	`}`
48	`}`

1	`#include <string>`
2	`#include <vector>`
3	`#include <unordered_map>`
4	`#include <unordered_set>`
5	`#include <queue>`
6
7	`using namespace std;`
8
9	`class Solution {`
10	`public:`
11	`int ladderLength(string beginWord, string endWord, vector<string>& wordList) {`
12	`unordered_set<string> wordSet(wordList.begin(), wordList.end());`
13	`if (wordSet.find(endWord) == wordSet.end()) {`
14	`return 0;`
15	`}`
16
17	`unordered_map<string, vector<string>> nei;`
18	`vector<string> extendedWordList = wordList;`
19	`extendedWordList.push_back(beginWord);`
20
21	`for (const string& word : extendedWordList) {`
22	`for (int j = 0; j < (int)word.size(); ++j) {`
23	`string pattern = word.substr(0, j) + "*" + word.substr(j + 1);`
24	`nei[pattern].push_back(word);`
25	`}`
26	`}`
27
28	`unordered_set<string> visit;`
29	`visit.insert(beginWord);`
30	`queue<string> q;`
31	`q.push(beginWord);`
32	`int res = 1;`
33
34	`while (!q.empty()) {`
35	`int size = (int)q.size();`
36	`for (int i = 0; i < size; ++i) {`
37	`string word = q.front();`
38	`q.pop();`
39	`if (word == endWord) {`
40	`return res;`
41	`}`
42	`for (int j = 0; j < (int)word.size(); ++j) {`
43	`string pattern = word.substr(0, j) + "*" + word.substr(j + 1);`
44	`for (const string& neiWord : nei[pattern]) {`
45	`if (visit.find(neiWord) == visit.end()) {`
46	`visit.insert(neiWord);`
47	`q.push(neiWord);`
48	`}`
49	`}`
50	`}`
51	`}`
52	`++res;`
53	`}`
54	`return 0;`
55	`}`
56	`};`

1	`var ladderLength = function(beginWord, endWord, wordList) {`
2	`if (!wordList.includes(endWord)) {`
3	`return 0;`
4	`}`
5
6	`const nei = new Map();`
7	`const extendedWordList = wordList.slice();`
8	`extendedWordList.push(beginWord);`
9
10	`for (const word of extendedWordList) {`
11	`for (let j = 0; j < word.length; j++) {`
12	`const pattern = word.slice(0, j) + '*' + word.slice(j + 1);`
13	`if (!nei.has(pattern)) {`
14	`nei.set(pattern, []);`
15	`}`
16	`nei.get(pattern).push(word);`
17	`}`
18	`}`
19
20	`const visit = new Set([beginWord]);`
21	`const q = [beginWord];`
22	`let front = 0;`
23	`let res = 1;`
24
25	`while (front < q.length) {`
26	`const size = q.length - front;`
27	`for (let i = 0; i < size; i++) {`
28	`const word = q[front++];`
29	`if (word === endWord) {`
30	`return res;`
31	`}`
32	`for (let j = 0; j < word.length; j++) {`
33	`const pattern = word.slice(0, j) + '*' + word.slice(j + 1);`
34	`const neighbors = nei.get(pattern) \|\| [];`
35	`for (const neiWord of neighbors) {`
36	`if (!visit.has(neiWord)) {`
37	`visit.add(neiWord);`
38	`q.push(neiWord);`
39	`}`
40	`}`
41	`}`
42	`}`
43	`res++;`
44	`}`
45	`return 0;`
46	`};`

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)`