1 import string 2 import collections 3  4 class Solution(object): 5     def findLadders(self, begin, end, words_list): 6         ‘‘‘删除起至单词‘‘‘ 7         words_list.discard(begin) 8         words_list.discard(end) 9 10         ‘‘‘根据tree递归构造路径‘‘‘11         def construct_paths(source, dest, tree):12             if source == dest: 13                 return [[source]]14             return [[source] + path for succ in tree[source]15                                     for path in construct_paths(succ, dest, tree)]16         17         ‘‘‘广度优先遍历分层搜索‘‘‘18         def bfs_level(this_lev, endw, tree, words_set):19             if not this_lev: return False20             for word in (this_lev):21                 words_set.discard(word)22             next_lev, done = set(), False23             while this_lev:24                 word = this_lev.pop()25                 for c in string.ascii_lowercase:26                     for index in range(len(word)):27                         neigh = word[:index] + c + word[index+1:]28                         if neigh == endw:29                             done = True30                             tree[word].append( neigh )31                         if not done and neigh in words_set:32                             next_lev.add(neigh)33                             tree[word].append( neigh )34             return done or bfs_level(next_lev, endw, tree, words_set)35 36         37         tree, path, paths = collections.defaultdict(list), [begin], []38         is_found = bfs_level(set([begin]), end, tree, words_list)39         return construct_paths(begin, end, tree)