126._Word_Ladder_II.md

126. Word Ladder II

题目:

https://leetcode.com/problems/word-ladder-ii/

难度:

Hard

其实关键在于怎么优化和表示图

思路来自1p3a：

这题目实在是太适合python了  如此简洁

就是基本的bfs，典型的level order traverse 有两个坑：

1. 不要判断字典里的某两个word是否只相差一个字母，而是要判断某个word的邻居（和他只相差一个字母的所有word）是否在字典里，这样的改进会使这一步的复杂度下降很多，否则超时妥妥
2. 每一轮访问过的word一定要从字典中删除掉，否则一定会超时

最后见到end word就收 完成

拿题目的例子来看：

		hit
	     |
	    hot
       /   \
      dot   lot
       |     |
      dog   log
        \   /
         cog

routine 字典，然后再根据这个来寻找路径

{'cog': ['log', 'dog'], 'hit': [], 'log': ['lot'], 'dog': ['dot'], 'hot': ['hit'], 'lot': ['hot'], 'dot': ['hot']}

'cog': ['log', 'dog']这里的意思就是说在走到'cog'之前尝试过了'log'和'dog'，即previous tried node

而生成字典的过程就是BFS的，此处保证寻找的路径就是最短的。

AC代码：

class Solution(object):
    def findLadders(self, beginWord, endWord, wordList):
        """
        :type beginWord: str
        :type endWord: str
        :type wordList: List[str]
        :rtype: List[List[str]]
        """

        def backtrack(result, trace, path, word):
            if len(trace[word]) == 0:
                result.append([word] + path)
            else:
                for prev in trace[word]:
                    backtrack(result, trace, [word] + path, prev)

        lookup = set(wordList) | set([beginWord])
        res, cur, routine = [], set([beginWord]), {word: [] for word in lookup}
        while cur and endWord not in cur:
            next_queue = set()
            for word in cur:
                lookup.remove(word)
            for word in cur:
                for i in range(len(word)):
                    for j in 'abcdefghijklmnopqrstuvwxyz':
                        candidate = word[:i] + j + word[i + 1:]
                        if candidate in lookup:
                            next_queue.add(candidate)
                            routine[candidate].append(word)
            cur = next_queue

        if cur:
            backtrack(res, routine, [], endWord)
        return res

这样可以beat 69.09%