126. Word Ladder II

Problem Statement

link: https://leetcode.com/problems/word-ladder-ii/ https://leetcode.cn/problems/word-ladder-ii/

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 si for 1 <= 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].

Example:

Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"] Output: [["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"]]

Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"] Output: []

Solution Approach

To find all shortest transformation sequences, we’ll employ Breadth First Search (BFS) to traverse the word ladder, while using a hashing technique to find words differing by one character.

Algorithm

1. Hashing Words: Firstly, construct a dictionary (edge) where keys are words with one character replaced by “_”, and values are lists of words in wordList that match the key. This aids in finding words differing by a single character.
2. BFS Traversal: Initialize a queue (q) with beginWord and its transformation sequences. For every word w in the current queue, check its possible transformations using the edge dictionary. If the transformation matches endWord, append the sequence to the results (res); else, add the transformations to the next level’s queue.
3. Pruning: To ensure only the shortest paths are considered, after processing each level of BFS, remove words in the current level from wordList. This ensures no further BFS levels will explore them, preventing longer paths from being considered.

Implement

    class Solution:
  def findLadders(self, beginWord: str, endWord: str, wordList: List[str]) -> List[List[str]]:
      wordList = set(wordList)
      res = []
      edge = defaultdict(list)
      for word in wordList:
          for i in range(len(word)):
              edge[word[:i] + "_" + word[i+1:]].append(word)
              
      q = {beginWord: [[beginWord]]}
      while q:
          wordList -= set(q.keys())
          new_q = collections.defaultdict(list)
          for w in q:
              if w == endWord: 
                  res += q[w]
              else:
                  for i in range(len(w)):
                      for neww in edge[w[:i] + "_" + w[i+1:]]:
                          if neww in wordList:
                              new_q[neww] += [j + [neww] for j in q[w]]          
          q = new_q
      return res
 

    
    

Twitter  facebook  Email