126 Word ladder II

beginWord = "hit"

endWord = "cog"

wordList = ["hot","dot","dog","lot","log"]

As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog", return its length 5.

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

思路： 就是一个DFS。然后存一个visited免得重走。

import collections
class Solution(object):
    def ladderLength(self, beginWord, endWord, wordList):
        """
        :type beginWord: str
        :type endWord: str
        :type wordList: Set[str]
        :rtype: int
        """
        # construct next possible dic
        dic = collections.defaultdict(list)
        wordList.add(endWord)
        for w in wordList:
            for i in range(len(w)):
                tmp = w[:i] + '_' + w[i+1:]
                dic[tmp].append(w)

        q = [[beginWord, [beginWord]]]

        visited = set()
        # BFS
        while q:
            k = len(q)
            for i in range(k):
                tmp = q.pop(0)
                w, path = tmp[0], tmp[1]
                # if hit the end. return
                if w==endWord:
                    return len(path)
                # else construct next possible path
                if w not in visited:
                    visited.add(w)
                    for i in range(len(w)):
                        key = w[:i] + '_' + w[i+1:]
                        if key in dic:
                            children = dic[key]
                            for c in children:
                                if c not in path:
                                    new = path + [c]
                                    q.append([c, new])
        return 0



wordList = {"hot","dot","dog","lot","log"}
beginWord = "hot"
endWord = "dog"

so = Solution()
a = so.ladderLength(beginWord, endWord, wordList)
print(a)

写一个ladderII

import collections
class Solution(object):
    def findLadders(self, beginWord, endWord, wordlist):
        """
        :type beginWord: str
        :type endWord: str
        :type wordlist: Set[str]
        :rtype: List[List[int]]
        """

        dic = collections.defaultdict(set)

        for w in wordlist+[endWord]:
            for i in range(len(w)):
                tmp = w[:i] +'_'+ w[i+1:]
                dic[tmp].add(w)

        res = []
        q = [(beginWord, [beginWord])]
        while q:
            word, path = q.pop(0)
            if not res or len(path)<len(res[0]):
                for i in range(len(word)):
                    tmp = word[:i] +'_'+ word[i+1:]
                    if tmp in dic:
                        children = dic[tmp]
                        for c in children:
                            if c not in path:
                                if c==endWord:
                                    res.append(path+[c])
                                q.append((c, path+[c]))
        return res

beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]
so = Solution()
ans = so.findLadders(beginWord, endWord, wordList)
print ans