Skip to main content

Word ladder II solution

Problem Description​

A transformation sequence from word beginWord to word endWord using a dictionary wordList is a sequence of words beginWord s1−>s2−>...−>sks1 -> s2 -> ... -> sk such that:

Every adjacent pair of words differs by a single letter. Every si for 1<=i<=k1 <= i <= k is in wordList. Note that beginWord does not need to be in wordList. 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.

Constraints​

  • 1<=beginWord.length<=51 <= beginWord.length <= 5
  • endWord.length==beginWord.lengthendWord.length == beginWord.length
  • 1<=wordList.length<=5001 <= wordList.length <= 500
  • wordList[i].length==beginWord.lengthwordList[i].length == beginWord.length
  • beginWord, endWord, and wordList[i] consist of lowercase English letters.
  • beginWord != endWord
  • All the words in wordList are unique.
  • The sum of all shortest transformation sequences does not exceed 105.

Solution for Word Ladder II Problem​

Approach :​

Intuition​

Define a helper function neighbors(word) that generates all the possible words by changing a single character in the given word. Initialize a variable words as a dictionary with beginWord as the key and a lambda function returning [[beginWord]] as the value. This dictionary will keep track of all possible transformation sequences. Initialize a set unvisited containing all words in wordList except beginWord. Perform BFS: While there are words in words and endWord is not yet found in words: Increment a counter i. Initialize a new dictionary new_words to store the next layer of words. Iterate through each word s in words: Generate all possible neighbors ss of s. If ss is in unvisited, create a lambda function get_seqs that appends ss to each sequence of words ending with s, and add ss and get_seqs to new_words. Update words to new_words. Remove the keys of new_words from unvisited. Return the transformation sequences ending with endWord.

Code in Different Languages​

Written by @mahek0620
 class Solution:
def findLadders(
self, beginWord: str, endWord: str, wordList: List[str]
) -> List[List[str]]:
def neighbors(word):
for i in range(len(word)):
for char in "abcdefghijklmnopqrstuvwxyz":
yield word[:i] + char + word[i + 1 :]

i = 1
words = {beginWord: lambda: [[beginWord]]}
unvisited = set(wordList)
while words and endWord not in words:
i += 1
new_words = defaultdict(lambda: lambda: [])
for s in words:
for ss in neighbors(s):
if ss in unvisited:

def get_seqs(capture=(ss, new_words[ss], words[s])):
ss, ss_get_seqs, s_get_seqs = capture
seqs = ss_get_seqs()
for seq in s_get_seqs():
seq.append(ss)
seqs.append(seq)
return seqs

new_words[ss] = get_seqs
words = new_words
unvisited -= words.keys()
return words[endWord]()

References​