126. Word Ladder II

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

1. Only one letter can be changed at a time.
2. 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 0 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.

Solution: Two-End BFS & DFS

import string
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]]
        """
        words = set(wordList)
        graph = self.bfs(beginWord, endWord, words)
        return self.dfs(graph, beginWord, endWord)

    def bfs(self, start, end, words):
        graph = collections.defaultdict(list)
        front, back = {start}, {end} & words
        words.discard(start)
        words.discard(end)
        while front and back and not front & back:
            small, large = (front, back) if len(front) < len(back) else (back, front)
            border = set()
            for word in small:
                for neighbor in self.neighbors(word):
                    if neighbor in words or neighbor in large:
                        border.add(neighbor)
                        if small is front:
                            graph[word].append(neighbor)
                        else:
                            graph[neighbor].append(word)
            words -= border
            if small is front:
                front = border
            else:
                back = border
        return graph

    def dfs(self, graph, start, end):
        paths = []
        path = []

        def _dfs(node):
            if node == end:
                paths.append(path + [end])
                return
            path.append(node)
            for neighbor in graph.get(node, []):
                _dfs(neighbor)
            path.pop()

        _dfs(start)
        return paths

    def neighbors(self, word):
        for idx, char in enumerate(word):
            for letter in string.lowercase:
                if char != letter:
                    yield word[:idx] + letter + word[idx + 1:]

Lessons:

• Two-end BFS builds a directed graph from beginWord to endWord.

Related:

• 127. Word Ladder