Word Ladder II
BFS & DFS Problems DSA practice problem on Onlearn.
Difficulty: hard.
Topics: Finding all shortest transformation sequences between two words using a word list (Word Ladder II problem), Graph, Breadth-First Search, Queue, Hash Map, String Manipulation, Time Complexity, Space Complexity, Graph Traversal, visited tracking, path reconstruction, shortest path algorithms, string algorithms, bfs, traversal, Shortest Path (Unweighted), Graph Traversal Utilities, Word Ladder Problem.
Given two distinct words startWord and targetWord, and a list wordList containing unique words of equal lengths. Find all shortest transformation sequence(s) from startWord to targetWord. A transformation sequence is a sequence of words w 1, w 2, ..., w k such that: 1. w 1 = startWord 2. w k = targetWord 3. For each i from 1 to k 1, w i and w {i+1} differ by exactly one letter. 4. Each w i (for 1 <= i <= k) must exist in wordList, including targetWord. startWord may or may not be part of the wordList. Return an empty list if there is no such transformation sequence. Note: All words consist of lowercase English characters. Input Specification: The first line contains startWord. The second line contains targetWord. The third line contains a list of strings wordList. Output Specification: Return a list of lists of strings, where each inner list represents a shortest transformation sequence from startWord to targetWord. Examples: Example 1: Input: startWord = "der" targetWord = "dfs" wordList = {"des", "der", "dfr", "dgt", "dfs"} Output: [ [ "der", "dfr", "dfs" ], [ "der", "des", "dfs"] ] Explanation: The length of the smallest transformation sequence here is 3. Following are the only two shortest ways to get to the targetWord from the startWord: "der" (replace ‘r’ by ‘s’) "des" (replace ‘e’ by ‘f’) "dfs". "der" (replace ‘e’ by ‘f’) "dfr" (replace ‘r’ by ‘s’) "dfs". Example 2: Input: startWord = "gedk" targetWord= "geek" wordList = {"geek", "gefk"} Output: [ [ "gedk", "geek" ] ] Explanation: The length of the smallest transformation sequence here is 2. Following is the only shortest way to get to the targetWord from the startWord: "gedk" (replace ‘d’ by ‘e’) "geek".