Word Ladder

此题需要对起始词的每一个位置进行另外25个字母的替换从而找到一个one step之内的词且此词在wordList之内，比较trick的地方在于需要每次找到这样一个词之后把这个词从wordList中删除，因为是BFS，当到达此词时肯定已经是最短路径了，所以不需要其他方法了，下面是代码

class Solution(object):
    def ladderLength(self, beginWord, endWord, wordList):
        """
        :type beginWord: str
        :type endWord: str
        :type wordList: List[str]
        :rtype: int
        """
        q = collections.deque([[beginWord, 1]])
        wordList = set(wordList)

        while q:
            base, step = q.pop()
            if base == endWord:
                return step
            for i in xrange(len(base)):
                left, right = base[ : i], base[i + 1 : ]
                for j in xrange(ord('a'), ord('{')):
                    if chr(j) == base[i]:
                        continue
                    nxtWord = left + chr(j) + right
                    if nxtWord in wordList:
                        wordList.remove(nxtWord)
                        q.appendleft([nxtWord, step + 1])

        return 0