难度: Hard
原题连接
内容描述
Given two words (beginWord and endWord), and a dictionary's word list, find all shortest transformation sequence(s) from beginWord to endWord, such that:
Only one letter can be changed at a time
Each transformed word must exist in the word list. Note that beginWord is not a transformed word.
Note:
Return an empty list 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:
[
["hit","hot","dot","dog","cog"],
["hit","hot","lot","log","cog"]
]
Example 2:
Input:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]
Output: []
Explanation: The endWord "cog" is not in wordList, therefore no possible transformation.
思路 1 - 时间复杂度: O(len(word) * len(dictionary))- 空间复杂度: O(len(word))******
其实关键在于怎么优化和表示图
思路来自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代码：
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%