Skip to content
HardStringsAI interview only

Word Ladder II

Asked atamazongooglemetamicrosoftuberbloomberglinkedin

01 · Problem

A word ladder from beginWord to endWord is a list of words beginWord -> w1 -> w2 -> ... -> endWord where:

  • each consecutive pair of words differs in exactly one letter position,
  • every word after beginWord (including endWord) is taken from wordList, and
  • no word appears twice in the same ladder.

beginWord itself does not need to be in wordList.

Return all ladders of the shortest possible length, each as a list of words starting with beginWord and ending with endWord. If no ladder exists, return an empty list []. The ladders may be returned in any order (the examples list them sorted for readability), but the words inside each ladder must be in path order.

02 · Examples

Example 01
Input
beginWord = "cat", endWord = "dog", wordList = ["cot","cog","dog","dat","dot"]
Output
[["cat","cot","cog","dog"],["cat","cot","dot","dog"],["cat","dat","dot","dog"]]

Three ladders of length 4 exist: cat -> cot -> cog -> dog, cat -> cot -> dot -> dog and cat -> dat -> dot -> dog. No ladder with 3 words exists because "cat" and "dog" differ in every position.

Example 02
Input
beginWord = "cold", endWord = "warm", wordList = ["cord","card","ward","warm","word","worm"]
Output
[["cold","cord","card","ward","warm"],["cold","cord","word","ward","warm"],["cold","cord","word","worm","warm"]]

Both "card" and "word" lead toward "ward"/"worm"; the shortest ladders have 5 words each: cold -> cord -> card -> ward -> warm, cold -> cord -> word -> ward -> warm and cold -> cord -> word -> worm -> warm.

Example 03
Input
beginWord = "hot", endWord = "dog", wordList = ["hat","hit","dot"]
Output
[]

"dog" is not in wordList, so no ladder can end there.

03 · Constraints

  • 011 <= beginWord.length <= 5
  • 02endWord.length == beginWord.length and every word in wordList has that same length
  • 031 <= wordList.length <= 500, and all words in wordList are distinct
  • 04All words consist of lowercase English letters, and beginWord != endWord
  • 05The total number of shortest ladders does not exceed 105

04 · Optimal complexity

Time
O(N * L * 26 + P)
Space
O(N * L)
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