DIY: Word Ladder I

Solve the interview question "Word Ladder I" in this lesson.

Problem statement

You are given a list of words, a startingWord, and an endingWord. This problem requires you to find the minimum number of transitions required to convert the startingWord into the endingWord under the following constraints:

  • All the words should be of 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:

4

One shortest transformation can be "hit" -> "hot" -> "dot" -> "dog" -> "cog". It can be seen that it took 4 steps to reach the last word.

Coding exercise

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

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