题目来源：
https://leetcode.com/problems/word-ladder-ii/
题意分析：
给定一个beginWord和一个endWord，以及一个字典单词，找出所有从beginWord变成endWord的所有最短路径，单词变化每次只能变一个字母，所变的字母必须在字典里面。
题目思路：
这是一个最短路径问题。首先将beginWord放进队列，当队列不为空的时候，pop出第一个数，将它周围的在字典的push进队列。要注意的是将字段的数push进队列的同时，将其路径用dict记录下来。
代码（python）：
1 class Solution(object): 2 def findLadders(self, beginWord, endWord, wordlist): 3 """ 4 :type beginWord: str 5 :type endWord: str 6 :type wordlist: Set[str] 7 :rtype: List[List[int]] 8 """ 9 ans,q = {},[]10 q.append(beginWord)11 ans[beginWord] = [[beginWord]]12 ans[endWord] = []13 while len(q) != 0:14 tmp = q.pop(0)15 for i in range(len(beginWord)):16 part1,part2 = tmp[:i],tmp[i + 1:]17 for j in "abcdefghijklmnopqrstuvwxyz":18 if tmp[i] != j:19 newword = part1 + j + part220 if newword == endWord:21 for k in ans[tmp]:22 ans[endWord].append(k + [endWord])23 while len(q) != 0:24 tmp1 = q.pop(0)25 if len(ans[tmp1][0]) >= len(ans[endWord][0]):26 break27 for ni in range(len(beginWord)):28 npart1,npart2 = tmp1[:ni],tmp1[ni+1:]29 for nj in "abcdefghijklmnopqrstuvwxyz":30 if tmp1[ni] != nj:31 nw = npart1 + nj + npart232 if endWord == nw:33 for nk in ans[tmp1]:34 ans[endWord].append(nk + [endWord])35 break36 if newword in wordlist:37 q.append(newword)38 ans[newword] = []39 for k in ans[tmp]:40 ans[newword].append(k + [newword])41 wordlist.remove(newword)42 elif newword in ans and len(ans[newword][0]) == len(ans[tmp][0]) + 1:43 for k in ans[tmp]:44 ans[newword].append(k + [newword])45 return ans[endWord]46 47