Skip to main content

127. Word Ladder

hard

Transform beginWord to endWord by changing one letter at a time, with every intermediate word in the dictionary. Return the shortest transformation length. Treat words as graph nodes and one-letter-apart pairs as edges — BFS finds the shortest path.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

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: every adjacent pair of words differs by a single letter; every si for 1 <= i <= k is in wordList (beginWord does not need to be in wordList); and sk == endWord. Given two words, beginWord and endWord, and a dictionary wordList, return the number of words in the shortest transformation sequence from beginWord to endWord, or 0 if no such sequence exists.

Constraints

  • 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
  • All the words in wordList are unique.

Examples

Example 1

Input
beginWord = 'hit', endWord = 'cog', wordList = ['hot','dot','dog','lot','log','cog']
Output
5

Explanation: One shortest transformation sequence is 'hit' -> 'hot' -> 'dot' -> 'dog' -> 'cog', which is 5 words long.

Example 2

Input
beginWord = 'hit', endWord = 'cog', wordList = ['hot','dot','dog','lot','log']
Output
0

Explanation: endWord 'cog' is not in wordList, therefore there is no valid transformation sequence.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Word transformations form a graph; BFS from beginWord gives the shortest path.

Hint 2

Building an explicit O(N^2 * L) adjacency list is too slow. Instead, precompute pattern buckets: for each word, generate L wildcard patterns ('h*t', '*it', 'hi*') and group words by pattern.

Hint 3

BFS the patterns: from the current word, generate its L patterns, jump to every word in those buckets, mark visited. Empty the bucket after visiting so you don't revisit.

Solution approach

Reveal approach

Edge case: if endWord isn't in wordList, return 0. Build a wildcard pattern -> list of words map: for each word of length L, generate L wildcard patterns like 'h*t' / '*it' / 'hi*' and append the word to each pattern's bucket. BFS from beginWord with a queue of (word, level) starting at level 1. For each dequeued word: if it equals endWord, return level. Otherwise generate its L wildcard patterns, walk the corresponding buckets, enqueue each new word at level+1 if not visited, mark visited, and clear the bucket (so other words don't reach it again — saves time). Return 0 when the queue drains. Bidirectional BFS from both ends meeting in the middle is the optimal version. O(N * L^2) time, O(N * L^2) space for the pattern map.

Complexity

Time
O(N * L^2)
Space
O(N * L^2)

Related patterns

  • bfs
  • graph
  • string

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Google
  • Meta
  • LinkedIn

Practice these live with InterviewChamp.AI

Drill Word Ladder and Graphs problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →