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，一层结束后把他们加到大的visited里面，记住每次要访问的word不可以是在visited里面的

最后见到end word就收 完成

拿题目的例子来看：

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

生成了如下的一个trace 字典，然后再根据这个来寻找路径

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

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

AC代码：

class Solution(object):
    def findLadders(self, beginWord, endWord, wordlist):
        """
        :type beginWord: str
        :type endWord: str
        :type wordlist: Set[str]
        :rtype: List[List[int]]
        """
        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)


        wordSet = set(wordlist) 
        wordSet.add(beginWord)
        wordSet.add(endWord)

        result, trace, current = [], {word: [] for word in wordSet}, set([beginWord])
        # print result, trace, current
        while current and endWord not in current:
        	for word in current:
        		wordSet.remove(word)
        	net = set([])
        	for word in current:
        		for i in range(len(word)):
        			for j in 'abcdefghijklmnopqrstuvwxyz':
        				candidate = word[:i] + j + word[i+1:]
        				if candidate in wordSet:
        					trace[candidate].append(word)
        					net.add(candidate)
        	current = net

        if current:
        	backtrack(result, trace, [], endWord)
        return result

这样可以beat 约 60%