卖萌的弱渣

I am stupid, I am hungry.

Word Ladder II

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

  1. Only one letter can be changed at a time
  2. Each intermediate word must exist in the word list

For example,

1
2
3
4
5
6
7
8
9

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.

Solution

(Word-Ladder2.py) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

class Solution(object):
    def findLadders(self, beginWord, endWord, wordlist):
        """
        :type beginWord: str
        :type endWord: str
        :type wordlist: Set[str]
        :rtype: List[List[int]]
        """
        # 把结尾单词插入list中
        wordlist.add(endWord)
        # BFS 每一层节点和他们的parents 
        level = set([beginWord])

        parents = collections.defaultdict(set)
        while level and endWord not in parents:
            next_level = collections.defaultdict(set)
            for word in level:
                for c in 'abcdefghijklmnopqrstuvwxyz':
                    for i in range(len(word)):
                        newWord = word[:i]+c+word[i+1:]
                        # 找到新单词
                        if newWord in wordlist and newWord not in parents:
                            # word 是 word的parents
                            next_level[newWord].add(word)
            level = next_level
            parents.update(next_level)

        # 从end word 开始建立结果
        res = [[endWord]]
        while res and res[0][0] != beginWord:
            res = [[p]+r for r in res for p in parents[r[0]]]
        return res