126 Word Ladder II
126. Word Ladder II
题目:
https://leetcode.com/problems/word-ladder-ii/
难度:
Hard
其实关键在于怎么优化和表示图
思路来自1p3a：
这题目实在是太适合python了 如此简洁
就是基本的bfs，典型的level order traverse 有两个坑：
- 不要判断字典里的某两个word是否只相差一个字母，而是要判断某个word的邻居（和他只相差一个字母的所有word）是否在字典里，这样的改进会使这一步的复杂度下降很多，否则超时妥妥
- 每一轮访问过的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代码：
```python
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%
