loading

Word Ladder — Step-by-Step Visualization

hardLeetCode #127Hash TableStringBreadth-First Search

A transformation sequence from word `beginWord` to word `endWord` using a dictionary `wordList` is a sequence of words `beginWord -> s1 -> s2 -> ... -> sk` such that: (1) Every adjacent pair of words differs by a single letter. (2) Every `si` is in `wordList`. (3) `sk == endWord`. Given two words and a dictionary, return the number of words in the shortest transformation sequence, or 0 if no such sequence exists.

Algorithm Pattern

Shortest Path BFS

Key Idea

This is a shortest path problem in an unweighted graph where each word is a node and an edge exists between words that differ by exactly one letter. BFS is the ideal algorithm for finding the shortest path. To optimize finding neighbors, we can use 'pattern' matching (e.g., `*ot` matches `hot`, `dot`, `lot`).

Step-by-Step Approach

  1. If `endWord` is not in `wordList`, return 0.
  2. Build a adjacency list using patterns: `hot` belongs to `*ot`, `h*t`, `ho*`.
  3. Use a queue for BFS, starting with `beginWord` and `level = 1`.
  4. Use a `visited` set to avoid cycles.
  5. For each word, generate all its patterns and visit all words sharing those patterns.
  6. The first time we reach `endWord`, return the current `level`.

Common Gotchas

  • Wait, the result is the number of *words* in the sequence, not the number of *edges*. So starting with `hit` is level 1.
  • Pattern matching with a dictionary is much faster than checking every word against every other word (O(N*L^2) vs O(N^2*L)).

Related Problems

← All problems