Given two words, beginWord and endWord, and a dictionary wordList, return all the shortest transformation sequences from beginWord to endWord, such that: 1. Only one letter can be changed at a time. 2. Each transformed word must exist in the wordList. Return an empty list if there is no such transformation sequence.
Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
Output: ["hit","hot","dot","dog","cog"]
Explanation: In this example, we need to transform "hit" to "cog" using the word list provided. The transformation is: "hit" -> "hot" -> "dot" -> "dog" -> "cog".
Input: beginWord = "hot", endWord = "dog", wordList = ["hot","dog"]
Output: ["hot","dog"]
Explanation: In this example, we can directly transform "hot" to "dog" as both words are in the word list.
Input: beginWord = "lost", endWord = "cost", wordList = ["most","fist","lost","cost","fish"]
Output: ["lost","cost"]
Explanation: In this example, we can transform "lost" to "cost" directly as both words are in the word list.
BFS with backtracking to find all possible transformations and then build the paths using DFS.
1from collections import deque
2from collections import defaultdict
3
4
5# Function to find all shortest transformation sequences from beginWord to endWord
6# using Word Ladder II
7
8def findLadders(beginWord, endWord, wordList):
9 # Check if endWord is not in the wordList
10 if endWord not in wordList:
11 return []
12
13 # Create a set for faster lookup
14 wordSet = set(wordList)
15
16 # Initialize variables
17 neighbors = defaultdict(list)
18 level = {beginWord: 0}
19 res = []
20 queue = deque([beginWord])
21
22 # BFS to build the graph and store the levels
23 while queue:
24 word = queue.popleft()
25 for i in range(len(word)):
26 for c in 'abcdefghijklmnopqrstuvwxyz':
27 newWord = word[:i] + c + word[i+1:]
28 if newWord in wordSet:
29 if newWord not in level:
30 level[newWord] = level[word] + 1
31 queue.append(newWord)
32 neighbors[newWord].append(word)
33
34 # Backtrack to build the paths
35 def backtrack(path, word):
36 if word == beginWord:
37 res.append([beginWord] + path)
38 return
39 for prevWord in neighbors[word]:
40 if level[prevWord] + 1 == level[word]:
41 backtrack([word] + path, prevWord)
42
43 # Start the backtracking
44 backtrack([], endWord)
45
46 return resfindLadders('hit', 'cog', ['hot', 'dot', 'dog', 'lot', 'log', 'cog'])
Step 1
1from collections import deque
2from collections import defaultdictImport necessary libraries for using deque and defaultdict
State: deque and defaultdict libraries imported
Step 2
1def findLadders(beginWord, endWord, wordList):Define the function to find all shortest transformation sequences
State: Function definition with input parameters
Step 3
1if endWord not in wordList:
2 return []Check if the endWord is in the wordList, if not, return empty list
State: Check if endWord is in wordList
Step 4
1wordSet = set(wordList)Create a set for faster lookup of words in the wordList
State: Convert wordList to a set for faster lookup
Step 5
1neighbors = defaultdict(list)
2 level = {beginWord: 0}
3 res = []
4 queue = deque([beginWord])Initialize data structures for storing neighbors, levels, result, and queue
State: Initialize defaultdict, level dictionary, result list, and queue
Step 6
1while queue:
2 word = queue.popleft()
3 for i in range(len(word)):
4 for c in 'abcdefghijklmnopqrstuvwxyz':Perform BFS traversal and generate new words by changing each character
State: Perform BFS traversal and generate new words
Step 7
1newWord = word[:i] + c + word[i+1:]
2 if newWord in wordSet:Generate new word by replacing character at position i with all alphabets and check if it's in the wordSet
State: Generate new word and check if it's in wordSet
Step 8
1if newWord not in level:
2 level[newWord] = level[word] + 1
3 queue.append(newWord)
4 neighbors[newWord].append(word)Update levels and neighbors for the new word if it's not visited before
State: Update levels and neighbors for the new word
Step 9
1def backtrack(path, word):
2 if word == beginWord:
3 res.append([beginWord] + path)
4 returnBacktrack to build the paths from endWord to beginWord
State: Backtracking function definition
Step 10
1for prevWord in neighbors[word]:
2 if level[prevWord] + 1 == level[word]:
3 backtrack([word] + path, prevWord)Explore neighbors and backtrack to find all paths from endWord to beginWord
State: Exploring neighbors and backtracking
Step 11
1backtrack([], endWord)
2
3 return resStart backtracking with an empty path and endWord to find all paths
State: Start backtracking to find all paths
M is the length of each word and N is the total number of words in the input word list. Building the adjacency list takes O(M * N) time, and each transformation of a word to its neighbors takes O(M) time. In the worst case, we might have to explore all possible transformations, resulting in O(M^2 * N) time complexity.
N is the number of words in the word list, and L is the maximum length of a word
How it's used: Exploring nodes level by level, commonly used for shortest path problems
Where in code: Main algorithm for finding shortest path in graph problems
Example: Finding the shortest path in a maze
What: Not handling edge cases properly
Why: This can lead to incorrect outputs or runtime errors
How to avoid: Ensure your code accounts for all possible edge cases
What: Using inefficient data structures
Why: This can result in slow performance
How to avoid: Choose data structures like dictionaries or sets for efficient lookups