All problems

Word Ladder II

Hard · graph traversal

You are given a starting word begin_word, a target word end_word and a list of allowed words word_list. Every word has the same length and uses lowercase English letters only.

A ladder is a sequence of words that starts with begin_word and ends with end_word, where each word differs from the one before it in exactly one letter (same position, different letter), and every word after the first is in word_list. The starting word does not have to be in word_list, but the target word must be, otherwise no ladder exists.

Return every shortest ladder, that is every ladder with the fewest words. Each ladder is a list of words including both ends. Order the ladders so that they are in dictionary order: compare two ladders word by word, and the first difference decides which comes first (words are compared alphabetically). All the ladders returned have the same length.

If there is no ladder, return an empty list.

Examples

Example 1

Input: begin_word = "red", end_word = "tan", word_list = ["ted", "rad", "tad", "ran", "tan"]

Output: [["red", "rad", "ran", "tan"], ["red", "rad", "tad", "tan"], ["red", "ted", "tad", "tan"]]

The shortest ladders have 4 words. There are three of them, listed in dictionary order.

Example 2

Input: begin_word = "red", end_word = "tan", word_list = ["ted", "rad", "tad"]

Output: []

"tan" is not in the list, so no ladder can end there.

Example 3

Input: begin_word = "cat", end_word = "cot", word_list = ["cot", "cut"]

Output: [["cat", "cot"]]

Changing one letter reaches "cot" directly. The route through "cut" has three words, so it is not a shortest ladder.

Constraints