word ladder 2

Given two words (beginWord and endWord), and a dictionary’s word list, find all shortest transformation sequence(s) from beginWord to endWord, such that:

Only one letter can be changed at a time
Each intermediate word must exist in the word list
For example,

Given:
beginWord = “hit”
endWord = “cog”
wordList = [“hot”,”dot”,”dog”,”lot”,”log”]
Return
[
[“hit”,”hot”,”dot”,”dog”,”cog”],
[“hit”,”hot”,”lot”,”log”,”cog”]
]
Note:
All words have the same length.
All words contain only lowercase alphabetic characters.

算法：
同样是最短路径问题，应该使用BFS。
但是，结果要求得到所有最短路径。
这时仅仅有BFS是不够的，我们需要构建从起点到终点的倒序图。
这就需要BFS以父层，子层遍历的形式进行搜索。
为了得到最后的路径，要利用生成的图从终点进行回溯，直到得到所有最短路径。

from collections import defaultdict


class Solution(object):
    def findLadders(self, start, end, wordDict):
        """
        :type start: str
        :type end: str
        :type dict: Set[str]
        :rtype: List[List[str]]
        """
        # first build the child - father tree. tree is implemented by dict
        # second get the path from the tree 
        tree = defaultdict(list)
        wordDict.add(end)
        curLevel = set()
        nextLevel = set()
        visited = set()
        curLevel.add(start)
        find = False
        while curLevel and not find:
            for node in curLevel:
                visited.add(node)
            for node in curLevel:
                for scss in self.successor(node, wordDict):
                    if scss == end:
                        find = True
                    if scss not in visited:
                        nextLevel.add(scss)
                        tree[scss].append(node)
            curLevel = nextLevel
            nextLevel = set()


        result = []
        print('tree is', tree)
        if find:
            path = []
            self.gener_path(tree, start, end, path, result)
        return result

    def gener_path(self, tree, start, word, path, result):

        path = path + [word]
        print(word, path, result)
        if start == word:
            result.append(list(reversed(path)))
        else:
            for father in tree[word]:
                self.gener_path(tree, start, father, path, result)






    def successor(self, curStr, wordDict):
        result = []
        curList = list(curStr)
        for idx in range(len(curStr)):
            for ele in 'abcdefghijklmnopqrstuvwxyz':
                temp = curList[idx]
                if ele != temp:
                    curList[idx] = ele
                    newStr = ''.join(curList)
                    curList[idx] = temp
                    if newStr in wordDict:
                        result.append(newStr)
        return result

solution =  Solution()
wordSet = set(["hot","cog","dog","tot","hog","hop","pot","dot"])
start = 'hot'
end = 'dog'

print(solution.findLadders(start,end,wordSet))

('tree is', defaultdict(<type 'list'>, {'hog': ['hot'], 'hop': ['hot'], 'pot': ['hot'], 'dog': ['hog', 'dot'], 'tot': ['hot'], 'cog': ['hog'], 'dot': ['hot']}))
('dog', ['dog'], [])
('hog', ['dog', 'hog'], [])
('hot', ['dog', 'hog', 'hot'], [])
('dot', ['dog', 'dot'], [['hot', 'hog', 'dog']])
('hot', ['dog', 'dot', 'hot'], [['hot', 'hog', 'dog']])
[['hot', 'hog', 'dog'], ['hot', 'dot', 'dog']]