127. Word Ladder

"""
Word Ladder
这道题自己卡了很久，主要是没想明白具体要怎么操作BFS，知道看了别人的代码以后，才形成了自己的思路。这道题要用到BFS，还是按照自己熟悉的那个套路来写。
这道题的思路是：
1）首先，要想明白在一个word中如何替换每一个letter，如果替换letter后的word出现在wordList中，就把那个word加到BFS的queue中。
1-1）替换letter的方法：
                    for i in range(0, len(word)):
                        for j in range(97,123): #这一步其实是在遍历26个英文字母的ASCII，然后用chr()把 ASCII 转成字母。
                            temp = word[:i] + chr(j) + word[i+1:] # 这个temp就是遍历每一个char的结果了。
2）BFS： 既然是BFS那么就要用到deque，首先把 beginWord 加到queue中，然后，用1-1的方法在wordList中寻找word，然后加到deque中。用len(q)确定每一层中含有的word个数，跑完一层word之后把res + 1。在这个过程中如果从deque中pop出来的word == endWrod了那么久返回res + 1。如果跑完所有的word还没有找到的话，最后返回 0
"""
class Solution(object):
    def ladderLength(self, beginWord, endWord, wordList):
        """
        :type beginWord: str
        :type endWord: str
        :type wordList: List[str]
        :rtype: int
        """
        st = set(wordList)

        q = collections.deque()
        q.append(beginWord)

        res = 0
        while q:
            num = len(q)
            for _ in range(num):
                word = q.popleft()
                if word == endWord:
                    return res + 1
                else:
                    for i in range(0, len(word)):
                        for j in range(97, 123):
                            temp = word[:i] + chr(j) + word[i+1:]
                            if temp in st and temp != word:
                                q.append(temp)
                                st.remove(temp)
            res += 1

        return 0