Solution: Word Ladder II
Explore how to find all shortest transformation sequences between two words by using a two-phase algorithm: BFS to discover shortest paths and DFS backtracking to reconstruct all valid sequences. Understand concepts like parent mapping, word set pruning, and time-space complexity in solving the Word Ladder II problem.
We'll cover the following...
Statement
You are given two words, beginWord and endWord, and a dictionary of words called wordList. Your task is to find all the shortest transformation sequences from beginWord to endWord, such that:
Only one letter can be changed at a time.
Each transformed word must exist in the given
wordList.The transformation sequence must begin with
beginWordand end withendWord.
Return all the shortest transformation sequences as a list of lists. If no valid transformation exists, return an empty list.
Constraints:
...