写了很久的一个做法，有点暴力，大概是bfs找到最大的lenth，然后通过回溯法找到解，剪枝的办法是判断当前如果已经>=lenth还没有到达最后单词就返回。代码如下：
class Solution(object):
def findLadders(self, beginWord, endWord, wordList):
"""
:type beginWord: str
:type endWord: str
:type wordList: List[str]
:rtype: List[List[str]]
"""
dic = {}
for w in wordList:
if w not in dic:
dic[w] = 1
q = [(beginWord,1)]
min_len = 0
while q:
e,lens = q.pop(0)
if e == endWord:
min_len = lens
break
for i in range(len(e)):
left = e[:i]
right = e[i + 1:]
for c in 'abcdefghigklmnopqrstuvwxyz':
if e[i] != c:
nextWord = left + c + right
if nextWord in dic:
q.append((nextWord,lens + 1))
del dic[nextWord]
dic = {}
for w in wordList:
if w not in dic:
dic[w] = 1
res = []
q = []
q.append(beginWord)
lenth = 1
self.dg(endWord, dic, res, q, lenth, min_len)
return res
def dg(self, endWord, dic, res, q, lenth, min_len):
e = q[-1]
if e == endWord and lenth == min_len:
temp = []
for i in q:
temp.append(i)
res.append(temp)
return
if lenth >= min_len:
return
for i in range(len(e)):
left = e[:i]
right = e[i+1:]
for c in 'abcdefghijklmnopqrstuvwxyz':
if e[i] != c:
nextword = left + c + right
if nextword in dic:
q.append(nextword)
del dic[nextword]
self.dg(endWord, dic, res, q, lenth + 1, min_len)
dic[nextword] = 1
q.pop()
