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 Sam K., 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

More Graphs practice problems

See all Graphs problems →