127-word-ladder¶
Try it on leetcode
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 the number of words in the shortest transformation sequence from beginWord to endWord, or 0 if no such sequence exists.
Example 1:
Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"] Output: 5 Explanation: One shortest transformation sequence is "hit" -> "hot" -> "dot" -> "dog" -> cog", which is 5 words long.
Example 2:
Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"] Output: 0 Explanation: The endWord "cog" is not in wordList, therefore there is no valid transformation sequence.
Constraints:
1 <= beginWord.length <= 10endWord.length == beginWord.length1 <= wordList.length <= 5000wordList[i].length == beginWord.lengthbeginWord,endWord, andwordList[i]consist of lowercase English letters.beginWord != endWord- All the words in
wordListare unique.
Solution(Python)¶
from collections import defaultdict
class Solution:
def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
return self.Bibfs(beginWord, endWord, wordList)
"""
Time Complexity: O(m^2*n)
Space Complexity: O(m^2*n)
"""
def bfs(self, beginWord, endWord, wordList):
"""
:type beginWord: str
:type endWord: str
:type wordList: List[str]
:rtype: int
"""
if endWord not in wordList or not endWord or not beginWord or not wordList:
return 0
# Since all words are of same length.
L = len(beginWord)
# Dictionary to hold combination of words that can be formed,
# from any given word. By changing one letter at a time.
all_combo_dict = defaultdict(list)
for word in wordList:
for i in range(L):
# Key is the generic word
# Value is a list of words which have the same intermediate generic word.
all_combo_dict[word[:i] + "*" + word[i + 1:]].append(word)
# Queue for BFS
queue = collections.deque([(beginWord, 1)])
# Visited to make sure we don't repeat processing same word.
visited = {beginWord: True}
while queue:
current_word, level = queue.popleft()
for i in range(L):
# Intermediate words for current word
intermediate_word = current_word[:i] + \
"*" + current_word[i + 1:]
# Next states are all the words which share the same intermediate state.
for word in all_combo_dict[intermediate_word]:
# If at any point if we find what we are looking for
# i.e. the end word - we can return with the answer.
if word == endWord:
return level + 1
# Otherwise, add it to the BFS Queue. Also mark it visited
if word not in visited:
visited[word] = True
queue.append((word, level + 1))
all_combo_dict[intermediate_word] = []
return 0
def __init__(self):
self.length = 0
# Dictionary to hold combination of words that can be formed,
# from any given word. By changing one letter at a time.
self.all_combo_dict = defaultdict(list)
def visitWordNode(self, queue, visited, others_visited):
queue_size = len(queue)
for _ in range(queue_size):
current_word = queue.popleft()
for i in range(self.length):
# Intermediate words for current word
intermediate_word = current_word[:i] + \
"*" + current_word[i + 1:]
# Next states are all the words which share the same intermediate state.
for word in self.all_combo_dict[intermediate_word]:
# If the intermediate state/word has already been visited from the
# other parallel traversal this means we have found the answer.
if word in others_visited:
return visited[current_word] + others_visited[word]
if word not in visited:
# Save the level as the value of the dictionary, to save number of hops.
visited[word] = visited[current_word] + 1
queue.append(word)
return None
"""
Time Complexity: O(m^2*n)
Space Complexity: O(m^2*n)
"""
def Bibfs(self, beginWord, endWord, wordList):
if endWord not in wordList or not endWord or not beginWord or not wordList:
return 0
# Since all words are of same length.
self.length = len(beginWord)
for word in wordList:
for i in range(self.length):
# Key is the generic word
# Value is a list of words which have the same intermediate generic word.
self.all_combo_dict[word[:i] + "*" + word[i + 1:]].append(word)
# Queues for birdirectional BFS
# BFS starting from beginWord
queue_begin = collections.deque([beginWord])
queue_end = collections.deque([endWord]) # BFS starting from endWord
# Visited to make sure we don't repeat processing same word
visited_begin = {beginWord: 1}
visited_end = {endWord: 1}
ans = None
# We do a birdirectional search starting one pointer from begin
# word and one pointer from end word. Hopping one by one.
while queue_begin and queue_end:
# Progress forward one step from the shorter queue
if len(queue_begin) <= len(queue_end):
ans = self.visitWordNode(
queue_begin, visited_begin, visited_end)
else:
ans = self.visitWordNode(queue_end, visited_end, visited_begin)
if ans:
return ans
return 0