Description:
A transformation sequence from word beginWord to word endWord using a dictionary wordList is a sequence of words beginWord -> s1 -> s2 -> ... -> sk such that:
- Every adjacent pair of words differs by a single letter.
- Every
sifor1 <= i <= kis inwordList. Note thatbeginWorddoes not need to be inwordList. sk == endWord
Given two words, beginWord and endWord, and a dictionary wordList, return all the shortest transformation sequences from beginWord to endWord, or an empty list if no such sequence exists. Each sequence should be returned as a list of the words [beginWord, s1, s2, ..., sk].
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 2 shortest transformation sequences:
"hit" -> "hot" -> "dot" -> "dog" -> "cog"
"hit" -> "hot" -> "lot" -> "log" -> "cog"
Example 2:
Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
Output: []
Explanation: The endWord "cog" is not in wordList, therefore there is no valid transformation sequence.Solution in Python:
Python
from collections import defaultdict, deque
from typing import List
class Solution:
def findLadders(self, beginWord: str, endWord: str, wordList: List[str]) -> List[List[str]]:
if endWord not in wordList:
return []
wordList = set(wordList)
wordList.add(beginWord)
# Initialize the BFS queue
queue = deque([beginWord])
# Dictionary to store the predecessors of each word
predecessors = defaultdict(list)
# Dictionary to store the distance of each word from beginWord
distances = {beginWord: 0}
while queue:
current_word = queue.popleft()
current_distance = distances[current_word]
for i in range(len(current_word)):
for c in 'abcdefghijklmnopqrstuvwxyz':
new_word = current_word[:i] + c + current_word[i+1:]
if new_word in wordList:
if new_word not in distances:
distances[new_word] = current_distance + 1
queue.append(new_word)
if distances[new_word] == current_distance + 1:
predecessors[new_word].append(current_word)
if endWord not in predecessors:
return []
# Function to build paths using DFS
def build_paths(word):
if word == beginWord:
return [[beginWord]]
paths = []
for predecessor in predecessors[word]:
for path in build_paths(predecessor):
paths.append(path + [word])
return paths
return build_paths(endWord)