DIY: Word Ladder II

Solve the interview question "Word Ladder II" yourself in this lesson.

We'll cover the following

Problem statement

In this scenario, you are given a list of words, a startingWord, and an endingWord. The problem requires you to find all shortest transformation sequences’ from startingWord to endingWord. There are a few conditions for this problem:

  • All the words should be the same length.

  • There should be no duplicates in the given list.

  • startingWord and endingWord should be non-empty.

  • startingWord and endingWord should not be the same.

  • A transition can only occur if two words differ by one character/alphabet.

  • It should return an empty list if there is no such transformation sequence.

  • All the words should contain only lowercase alphabetic characters.

Input

The following is an example input:

word_list = ["hot","dot","dog","lot","log","cog"]
start = "hit"
target = "cog"

Output

The following is an example output:

[
  ["hit","hot","dot","dog","cog"],
  ["hit","hot","lot","log","cog"]
]

It can be seen that hit can be converted to cog by following the above two sequences.

Coding exercise

For this coding exercise, you need to implement the wordLadder2(startingWord, endingWord, wordList) function. The function will return the shortest transformation sequences from startingWord to endingWord.

Level up your interview prep. Join Educative to access 80+ hands-on prep courses.