DIY: Word Ladder II

Problem statement

In this scenario, you are given a list of words, a starting_word, and an ending_word. The problem requires you to find all shortest transformation sequences’ from starting_word to ending_word. 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.

• 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"]
starting_word = "hit"
ending_word = "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 word_ladder2(starting_word, ending_word, word_list) function. The function will return the shortest transformation sequences from starting_word to ending_word.