127. Word Ladder

Given two words (beginWord and endWord), and a dictionary's word list, find the length of shortest transformation sequence 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"]

As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog", return its length 5.

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

import string


class Solution(object):
    def ladderLength(self, beginWord, endWord, wordList):
        """
        :type beginWord: str
        :type endWord: str
        :type wordList: List[str]
        :rtype: int
        """
        words = set(wordList)
        front, back = {beginWord}, {endWord} & words
        length = 2
        while front and back:
            if len(back) < len(front):
                front, back = back, front
            new_front = set()
            for word in front:
                for neighbor in self.neighbors(word):
                    if neighbor in back:
                        return length
                    if neighbor in words:
                        words.remove(neighbor)
                        new_front.add(neighbor)
            front = new_front
            length += 1
        return 0

    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:

• Each word is a node in graph, and its transformations are its neighbors.

Related:

• 126. Word Ladder II