[Leetcode] 127. Word Ladder

Another classical breadth first search problem. The framework should be simple:

    initialize queue
    while queue:
        pop up the cur_word, path
        for all possible nodes (by possible nodes, I mean it only differs one letter with cur_word and is in wordList ):
            if this word is end word: return
            else: enter into the queue

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.

UPDATE (2017/1/20):
The wordList parameter had been changed to a list of strings (instead of a set of strings). Please reload the code definition to get the latest changes.

Here is the code:

class Solution(object):
    def ladderLength(self, beginWord, endWord, wordList):
        """
        :type beginWord: str
        :type endWord: str
        :type wordList: List[str]
        :rtype: int
        """
        wordList = set(wordList)
        queue = collections.deque([(beginWord, 1)])
        
        while queue:
            cur_w, path = queue.pop()
            for i in range(len(cur_w)):
                for l in 'abcdefghijklmnopqrstuvwxyz':
                    trans_w = cur_w[:i] + l + cur_w[i+1:]
                    if trans_w in wordList:
                        if trans_w == endWord:
                            return path + 1
                        else:
                            queue.appendleft((trans_w, path + 1))
                        wordList.remove(trans_w)
        return 0