python实现leetcode之126. 单词接龙 II

解题思路

1.构造一副图，任何单词都与他将其中某一个字符替换为后的字符串临接
2.记住每个节点从beginWord开始的深度，使用广度优先遍历，第一次访问时深度是最浅的
3.构建一个队列queue进行广度优先遍历，queue中每个元素是最后一个节点访问的完整路径
4.length代表队列的最大长度，因为结果都是最短转换序列，所以出现一次结果后，长度再次被限制
5.进行广度优先遍历，在路径长度超过length是退出
6.对找到endWord的序列，将带有的节点过滤掉，剩下的就是路径

126. 单词接龙 II

代码

class Solution:
    def findLadders(self, beginWord, endWord, wordList):
        # 构造一副图，任何单词都与他将其中某一个字符替换为*后的字符串临接
        graph = build_graph([beginWord, *wordList])
        # 记住每个节点从beginWord开始的深度，使用广度优先遍历，第一次访问时深度是最浅的
        depth = {beginWord: 0}
        result = []
        # 队列中每个元素是最后一个节点访问的完整路径
        queue = [[beginWord]]
        length = len(wordList)*2 + 1  # 队列最多就这么长

        while queue:
            series = queue.pop(0)
            if len(series) >= length:
                break
            else:
                last = series[-1]
                for nb in graph[last]:
                    if nb not in depth:
                        depth[nb] = len(series)
                    if len(series) > depth[nb]:
                        continue  # 非第一次访问nb节点
                    if nb == endWord:
                        # 因为结果都是最短转换序列，所以出现一次结果后，长度再次被限制
                        length = len(series) + 1
                        result.append([*series, nb])
                    else:
                        # 该节点如果没有在边里出现过
                        if nb not in series:
                            queue.append([*series, nb])

        return [[wd for wd in item if '*' not in wd] for item in result]


def build_graph(words):
    graph = {}
    for word in words:
        if word not in graph:
            graph[word] = set()
        for i in range(len(word)):
            patt_wd = word[:i] + '*' + word[i+1:]
            if patt_wd not in graph:
                graph[patt_wd] = set()
            graph[word].add(patt_wd)
            graph[patt_wd].add(word)
    return graph