Word Ladder

Problem: Word Ladder

In this problem, we can search all the words in the set that can be transformed from beginning word step by step. If all possible-to-transform word are searched and our target word is still not visited, then the target is unreachable.

Code in Python:

from collections import deque

class Solution(object):
    def ladderLength(self, beginWord, endWord, wordList):
        """
        :type beginWord: str
        :type endWord: str
        :type wordList: Set[str]
        :rtype: int
        """
        queue = deque([(beginWord, 1)])
        letters = string.ascii_lowercase
        visited = set()
        while queue:
            word, dist = queue.popleft()
            if word == endWord:
                return dist 
            for i in xrange(len(word)):
                for c in letters:
                    if word[i] != c:
                        newWord = word[:i] + c + word[i+1:]
                        if newWord not in visited and newWord in wordList:
                            queue.append((newWord, dist+1))
                            visited.add(newWord)
        return 0