Skip to content
HardGraphsFree practice

Word Ladder

Asked atamazonmetagooglemicrosoftlinkedinbloombergapple

01 · 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. Note that beginWord does not need to be in wordList.
  • 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.

02 · Examples

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

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

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

The endWord "cog" is not in wordList, so no valid transformation sequence exists.

Example 03
Input
beginWord = "a", endWord = "c", wordList = ["a","b","c"]
Output
2

The transformation "a" -> "c" changes one letter and is 2 words long.

03 · Constraints

  • 011 <= beginWord.length <= 10
  • 02endWord.length == beginWord.length
  • 031 <= wordList.length <= 5000
  • 04wordList[i].length == beginWord.length
  • 05beginWord, endWord, and wordList[i] consist of lowercase English letters.
  • 06beginWord != endWord
  • 07All the words in wordList are unique.

04 · Optimal complexity

Time
O(M^2 * N)
Space
O(M^2 * N)
05 · Two ways to work on it

Practice it alone or rehearse it as an interview.

Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.

Start a voice interview on this problem