DIY: Word Ladder I

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

Problem statement

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

  • All the words should be of the same length.

  • There should be no duplicates in the given list.

  • starting_word and ending_word should be non-empty.

  • starting_word and ending_word 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 word_ladder(starting_word, ending_word, wordList) function. The function will return the shortest transformation from the starting_word to the ending_word.

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