127. Word Ladder

How to solve Word Ladder (LeetCode 127): the approach in brief

The problem

A transformation sequence from word beginWord to word endWord using a dictionary wordList is a sequence of words beginWord -> s1 -> s2 -> ... -> sk such that:

Pattern

Word Ladder is a Graph Traversal Patterns (DFS & BFS) problem, in the Graph BFS - Connected Components / Island Counting subpattern. The pattern covers DFS/BFS traversal, topological sort, shortest paths, Union-Find, and MST

Use BFS for shortest path in unweighted graphs. Solve word ladder, rotting oranges, and matrix problems.

Approach outline

1. Think of the problem as finding the shortest path in a graph where each node represents a word, and edges connect words that differ by exactly one letter.
2. To efficiently find neighbors for each word, consider how you can transform words by changing one letter at a time and check if the new word exists in the dictionary.
3. Breadth-first search (BFS) is well-suited here because it explores all words at the current transformation depth before moving deeper, ensuring the shortest path is found.

Complexity

The reference solution runs in O(N * L^2) time and O(N * L) space.

Asked at

Word Ladder has been reported in interviews at Amazon, Facebook, Lyft, Microsoft, Google, Uber, Bloomberg, Qualtrics.