【leetcode】126. Word Ladder II

题目如下：

解题思路：DFS或者BFS都行。本题的关键在于减少重复计算。我采用了两种方法：一是用字典dic_ladderlist记录每一个单词可以ladder的单词列表；另外是用dp数组记录从startword开始到wordlist每一个word的最小转换次数，这一点非常重要，可以过滤很多无效的运算。

代码如下：

class Solution(object):

    def getLadderList(self, w,d):

        l = []

        r = []

        for i in xrange(26):

            l.append(chr(i + ord('a')))

        for i in range(len(w)):

            for j in l:

                if w[i] != j:

                    v = w[:i] + j + w[i+1:]

                    if v in d:

                        r.append(v)

        return r

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

        #print len(wordList)

        dic = {}

        for i,v in enumerate(wordList):

            dic[v] = i

        if endWord not in dic:

            return []

        queue = [(beginWord,0,beginWord)]

        res = []

        shortest = len(wordList) + 1

        dp = [shortest for i in wordList]

        dic_ladderlist = {}

        while len(queue) > 0:

            word,count,path = queue.pop(0)

            if count > shortest:

                continue

            if word in dic_ladderlist:

                wl = dic_ladderlist[word]

            else:

                wl = self.getLadderList(word,dic)

                dic_ladderlist[word] = wl

            for i in wl:

                if dp[dic[i]] >= count+1 :

                    if i == endWord:

                        #path = path + ' ' + i

                        pl = path.split(' ')

                        pl.append(endWord)

                        if len(pl) < shortest:

                            res = []

                            res.append(pl)

                            shortest = len(pl)

                        elif len(pl) == shortest:

                            res.append(pl)

                            shortest = len(pl)

                        continue

                    queue.append((i,count + 1,path + ' ' + i))

                    dp[dic[i]] = count + 1

        return res