Word Ladder II

Problem: Word Ladder II

We can use BFS to search all the possible ladder from beginWord to endWord. However, this method can take a lot of time. To avoid this situation, we can use a two-end BFS to do search from beginWord and endWord to middle of ladder at the same time, thus avoid a lot of unnecessary operations. The solution is actually referenced from this one.

Code in Python:

class Solution(object):
    def findLadders(self, beginWord, endWord, wordlist):
        """
        :type beginWord: str
        :type endWord: str
        :type wordlist: Set[str]
        :rtype: List[List[int]]
        """
        fronts = [{beginWord}, {endWord}]
        parent = {beginWord: None, endWord: None}
        wordlist.discard(beginWord)
        wordlist.discard(endWord)
        ans = []
        while fronts[0] and fronts[1] and not ans:
            if len(fronts[0]) > len(fronts[1]):
                fronts.reverse()
            newlevel = set()
            for word in fronts[0]:
                for i in xrange(len(word)):
                    for char in string.lowercase:
                        newWord = word[:i] + char + word[i+1:]
                        if newWord in fronts[1]:
                            self.buildLadders(word, newWord, beginWord, parent, ans)
                        if newWord in newlevel:
                            parent[newWord].append(word)
                        if newWord in wordlist:
                            newlevel.add(newWord)
                            wordlist.remove(newWord)
                            parent[newWord] = [word]
            fronts[0] = newlevel
        return ans

    def buildLadders(self, aWord, bWord, beginWord, parent, ans):
        paths = [[], []]
        path = [aWord]
        self._build(parent, path, paths[0])
        path = [bWord]
        self._build(parent, path, paths[1])
        if paths[0][0][-1] != beginWord:
            paths.reverse()
        for path in paths[0]:
            path.reverse()
        for aPath in paths[0]:
            for bPath in paths[1]:
                ans.append(aPath + bPath)

    def _build(self, parent, path, paths):
        if not parent[path[-1]]:
            paths.append(path[:])
            return
        for nextWord in parent[path[-1]]:
            path.append(nextWord)
            self._build(parent, path, paths)
            path.pop()

Take what's in the problem as an example, we first do BFS from "hit" and get "hot" and mark parent of "hot" as "hit". We continue to get "dot" and "lot". This time we got more branch, thus do BFS from "cog" and found "dog" and "log", then we found there are ladders between "dot" and "dog", also "lot" and "log". So we can build ladders based on these results. There are also many details in the procedure of building ladders.