mafeshsho8lmafeshsho8l
Get Started
All coding questions

Word Ladder

hard
LeetCode Top 100graphsbfsstrings

Problem

Given a start word, an end word, and a dictionary of equal-length words, find the length of the shortest transformation sequence that changes the start into the end, altering exactly one letter at a time and keeping every intermediate word in the dictionary. Return zero if impossible.

Examples

Input: begin = "hit", end = "cog", words = ["hot","dot","dog","lot","log","cog"]
Output: 5
hit -> hot -> dot -> dog -> cog has five words.

Constraints

  • • 1 <= word length <= 10
  • • 1 <= dictionary size <= 5000
  • • All words share the same length
Hints(tap to reveal)
  • 1. Treat each word as a graph node.
  • 2. Breadth-first search finds the shortest path.
Optimal approach(spoiler)
  1. Model each word as a node; edges connect words differing by one letter.
  2. Run BFS from the start word, expanding by trying each single-letter change.
  3. Use the dictionary as a set for fast membership checks.
  4. Return the level at which the end word is first reached.
  5. Generic-pattern preprocessing keeps neighbour generation efficient.

Ready to solve it?

Write your solution in the editor and get an instant AI grade on correctness, edge cases, and complexity.

Practice in the editor