[LeetCode]题解（python）：126-Word Ladder II

题目来源：

　　https://leetcode.com/problems/word-ladder-ii/

---

题意分析：

　　给定一个beginWord和一个endWord，以及一个字典单词，找出所有从beginWord变成endWord的所有最短路径，单词变化每次只能变一个字母，所变的字母必须在字典里面。

---

题目思路：

　　这是一个最短路径问题。首先将beginWord放进队列，当队列不为空的时候，pop出第一个数，将它周围的在字典的push进队列。要注意的是将字段的数push进队列的同时，将其路径用dict记录下来。

---

代码（python）：

　　

 class Solution(object):

     def findLadders(self, beginWord, endWord, wordlist):

         """

         :type beginWord: str

         :type endWord: str

         :type wordlist: Set[str]

         :rtype: List[List[int]]

         """

         ans,q = {},[]

         q.append(beginWord)

         ans[beginWord] = [[beginWord]]

         ans[endWord] = []

         while len(q) != 0:

             tmp = q.pop(0)

             for i in range(len(beginWord)):

                 part1,part2 = tmp[:i],tmp[i + 1:]

                 for j in "abcdefghijklmnopqrstuvwxyz":

                     if tmp[i] != j:

                         newword = part1 + j + part2

                         if newword == endWord:

                             for k in ans[tmp]:

                                 ans[endWord].append(k + [endWord])

                             while len(q) != 0:

                                 tmp1 = q.pop(0)

                                 if len(ans[tmp1][0]) >= len(ans[endWord][0]):

                                     break

                                 for ni in range(len(beginWord)):

                                     npart1,npart2 = tmp1[:ni],tmp1[ni+1:]

                                     for nj in "abcdefghijklmnopqrstuvwxyz":

                                         if tmp1[ni] != nj:

                                             nw = npart1 + nj + npart2

                                             if endWord == nw:

                                                 for nk in ans[tmp1]:

                                                     ans[endWord].append(nk + [endWord])

                             break

                         if newword in wordlist:

                             q.append(newword)

                             ans[newword] = []

                             for k in ans[tmp]:

                                 ans[newword].append(k + [newword])

                             wordlist.remove(newword)

                         elif newword in ans and len(ans[newword][0]) == len(ans[tmp][0]) + 1:

                             for k in ans[tmp]:

                                 ans[newword].append(k + [newword])

         return ans[endWord]