127. Word Ladder

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.

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.

Example 1:

Input:
beginWord = "hit",
endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"]

Output: 5

Explanation: As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.

Example 2:

Input:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]

Output: 0

Explanation: The endWord "cog" is not in wordList, therefore no possible transformation.

解题要点：

用一个dict记录所有wordList里的字符组合（eg. hit: "#it", "h#t", "hi#")，如有分享同样字符，加到同一个字符key里。然后从startWord开始放进queue，再次根据字符组合到dict里寻找符合下一步的字。找到后检测是否等于endWord，如是，返回level + 1；若不是，检测是否visited，加进queue，并在level上增加1。

class Solution(object):
    def ladderLength(self, beginWord, endWord, wordList):
        """
        :type beginWord: str
        :type endWord: str
        :type wordList: List[str]
        :rtype: int
        """
        if endWord not in wordList:
            return 0
        n = len(beginWord)
        wordDict = dict()
        for word in wordList:
            for i in range(n):
                key = word[:i] + "#" + word[i+1:]
                if key in wordDict:
                    wordDict[key].append(word)
                else:
                    wordDict[key] = [word]
        # print wordDict
        visited = {}
        for wor in wordList:
            visited[wor] = 0
        queue = [(beginWord, 1)]
        while queue:
            w, level = queue.pop(0) 
            for j in range(n):
                key1 = w[:j] + "#" + w[j+1:]
                if key1 in wordDict:
                    for wo in wordDict[key1]:
                        if wo == endWord:
                            return level + 1
                        if visited[wo] == 0:
                            visited[wo] = 1
                            queue.append((wo, level + 1))
                    wordDict[key1] = []
        return 0