Word Ladder

Question

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.

Tags

• BFS
• Graph

Thought

Use BFS search here. Remember to remove the visited node in the graph to decrease the calculation time.

Code

class Solution(object):
    def ladderLength(self, beginWord, endWord, wordList):
        """
        :type beginWord: str
        :type endWord: str
        :type wordList: List[str]
        :rtype: int
        """
        word_set = set(wordList)
        if len(beginWord) != len(endWord) or endWord not in word_set:
            return 0
        queue = [(1, beginWord)]
        while queue:
            count, word = queue[0]
            del queue[0]
            if word == endWord:
                return count
            else:
                for i in xrange(len(word)):
                    for ch in 'abcdefghijklmnopqrstuvwxyz':
                        current_word = word[:i] + ch + word[i+1:]
                        if current_word in word_set:
                            queue.append((count+1, current_word))
                            word_set.remove(current_word)
        return 0