1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
| import string
import collections
class Solution(object):
def findLadders(self, begin, end, words_list):
'''删除起至单词'''
words_list.discard(begin)
words_list.discard(end)
'''根据tree递归构造路径'''
def construct_paths(source, dest, tree):
if source == dest:
return [[source]]
return [[source] + path for succ in tree[source]
for path in construct_paths(succ, dest, tree)]
'''广度优先遍历分层搜索'''
def bfs_level(this_lev, endw, tree, words_set):
if not this_lev: return False
for word in (this_lev):
words_set.discard(word)
next_lev, done = set(), False
while this_lev:
word = this_lev.pop()
'''这里有一个坑，oj把单词长度看做一个常数，要枚举26个字母'''
'''否则O(n*n)会超时tle'''
for c in string.ascii_lowercase:
for index in range(len(word)):
neigh = word[:index] + c + word[index+1:]
if neigh == endw:
done = True
tree[word].append( neigh )
if not done and neigh in words_set:
next_lev.add(neigh)
tree[word].append( neigh )
return done or bfs_level(next_lev, endw, tree, words_set)
tree, path, paths = collections.defaultdict(list), [begin], []
is_found = bfs_level(set([begin]), end, tree, words_list)
return construct_paths(begin, end, tree)
|
