Word Ladder II

Given a begin word, an end word, and a dictionary, return all of the shortest transformation sequences. Pattern focus: BFS shortest path in unweighted graph. Use BFS for minimum distance and parent tracking to reconstruct every shortest path.

Input Format

beginWord = start word, endWord = target word, wordList = dictionary

Output Format

all shortest transformation sequences

Constraints

  • 1 <= input size <= 10^5
  • -10^9 <= numeric values <= 10^9
  • beginWord, endWord, wordList must satisfy the format described in inputFormat.

Examples

Example 1:

Input:

beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log","cog"]

Output:

[["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"]]

Explanation:

There are two shortest transformation sequences of equal length.

Example 2:

Input:

beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]

Output:

[]

Explanation:

No valid sequence reaches the end word.

Loading...
Word Ladder II - Queue Deque DSA Problem