Word Ladder Problem

问题描述：
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:

Only one letter can be changed at a time
Each intermediate word must exist in the word list
For example,

Given:
beginWord = “hit”
endWord = “cog”
wordList = [“hot”,”dot”,”dog”,”lot”,”log”]
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.

算法：
搜索算法，求最短路径相关问题，应该用BFS。
只求路径长度，不需要具体路径。即要求遍历层数，用变量level标记层数，遇到终点返回层数level即可。

from collections import deque
class Solution(object):
    def ladderLength(self, beginWord, endWord, wordDict):
        """
        :type beginWord: str
        :type endWord: str
        :type wordDict: Set[str]
        :rtype: int
        """
        level = 1
        que = deque()
        visited = set()
        wordDict.add(endWord)
        que.append((beginWord, level)) # state is represented by (str, level depth)
        while que:
            curStr, curLevel = que.popleft()
            curLevel += 1
            for sucsr in self.successor(curStr, wordDict):
                if sucsr == endWord:
                    return curLevel
                if sucsr not in visited:
                    visited.add(sucsr)
                    wordDict.remove(sucsr)
                    que.append((sucsr,curLevel))
        return 0

    def successor(self, curStr, wordDict):
        succss = []
        curList = list(curStr)
        for idx in range(len(curStr)):
            for ele in 'abcdefghijklmnopqrstuvwxyz':
                temp = curList[idx]
                curList[idx] = ele
                newStr = ''.join(curList)
                curList[idx] = temp
                if newStr in wordDict:
                    succss.append(newStr)
        return succss



solution =  Solution()
wordSet = set(["hot","dot","dog","lot","log"])
start = 'hit'
end = 'cog'
print(solution.ladderLength(start,end,wordSet))


5