Word Ladder II

Question

Given two words (beginWord and endWord), and a dictionary's word list, find all shortest transformation sequence(s) from beginWord to endWord, such that:

Only one letter can be changed at a time Each transformed word must exist in the word list. Note that beginWord is not a transformed word. For example,

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

  [
    ["hit","hot","dot","dog","cog"],
    ["hit","hot","lot","log","cog"]
  ]

Note:

• Return an empty list if there is no such transformation sequence.
• All words have the same length.
• All words contain only lowercase alphabetic characters.
• You may assume no duplicates in the word list.
• You may assume beginWord and endWord are non-empty and are not the same.

Tags

• Array
• Backtracking
• BFS
• Graph

Thought

Reference: https://discuss.leetcode.com/topic/43603/fast-and-clean-python-c-solution-using-double-bfs-beats-98

Since we need to find all shortest path in the search, it is necessary to use the BFS in the backtracking. However, the normal backtracking algorithm will cause TLE easily especially when we are using Python. Thus, here we need to use 2-side backtracking algorithm:

1. We use a bfs function for performing BFS algorithm. However, we need to switch the direction when one layer is larger than the other layer (we called the layers from two sides are thisLev and otherLev and both of them are sets).
2. The BFS process will stop when the two sets have intersection, which means we have found the shortest path.
3. We use a tree (list of dictionary) to store all the neighboring relationships in the path.
4. We use a function called build_path to retrieve the possible paths from the tree according to the start word and the end word.
5. The function named add_path is used to grow the tree during the BFS process according to the direction.

Code

import collections

class Solution(object):
    def findLadders(self, beginWord, endWord, wordList):
        """
        :type beginWord: str
        :type endWord: str
        :type wordList: List[str]
        :rtype: List[List[str]]
        """
        def build_path(source, dest, tree):
            """
            Build the path from the source word to the dest word based on the tree
            :param source: 
            :param dest: 
            :param tree: 
            :return: 
            """
            if source == dest:
                return [[source]]
            return [[source] + path for succ in tree[source] for path in build_path(succ, dest, tree)]

        def add_path(tree, word, neigh, isForw):
            """
            Add the path info into the tree based on the word and the direction
            :param tree: 
            :param word: 
            :param neigh: 
            :param isForw: 
            :return: 
            """
            if isForw:
                tree[word].append(neigh)
            else:
                tree[neigh].append(word)

        def bfs(thisLev, otherLev, tree, isForw, wordSet):
            """
            run the 2-side BFS for the word ladder and build the tree
            :param thisLev: 
            :param otherLev: 
            :param tree: 
            :param isForw: 
            :param wordSet: 
            :return: 
            """
            if not thisLev:
                return False
            if len(thisLev) > len(otherLev):
                return bfs(otherLev, thisLev, tree, not isForw, wordSet)
            for word in (thisLev | otherLev):
                wordSet.discard(word)
            nextLev, done = set(), False
            while thisLev:
                word = thisLev.pop()
                for c in 'abcdefghijklmnopqrstuvwxyz':
                    for index in range(len(word)):
                        neigh = word[:index] + c + word[index+1:]
                        if neigh in otherLev:
                            done = True
                            add_path(tree, word, neigh, isForw)
                        if not done and neigh in wordSet:
                            nextLev.add(neigh)
                            add_path(tree, word, neigh, isForw)
            return done or bfs(nextLev, otherLev, tree, isForw, wordSet)

        wordSet = set(wordList)
        if endWord not in wordSet:
            return []
        tree = collections.defaultdict(list)
        bfs(set([beginWord]), set([endWord]), tree, True, set(wordList))
        return build_path(beginWord, endWord, tree)