首页 > 其他 > 详细

单词接龙 II

时间：2018-10-28 10:55:04 阅读：145 评论：0 收藏：0 [点我收藏+]

单词接龙 II （来自lintecode：https://www.lintcode.com/problem/word-ladder-ii/?_from=ladder&&fromId=1）

import copy
class Solution:
    graph = {}
    used = set()
    result = []
    def findLadders(self, start, end, dict):
        self.graph[start] = set()
        self.graph[end] = set()
        for word in dict:
            self.graph[word] = set()#先建立起空的有向图
        self.buildgraph(start, dict)
        self.buildgraph(end, dict)
        for word in dict:
            self.buildgraph(word, dict)#开始建立有向图
        dist = self.distance(end)#开始建立距离表
        self.findresult(start, end, dist, [])#根据距离建立result
        return self.result

    def buildgraph(self, word, dict):#建立有向图
        for char in range(len(word)):
            left = word[:char]
            right = word[char + 1:]
            for mid in "abcdefghijklmnopwrstuvwxyz":
                neword = left + mid + right
                if neword != word and neword in dict:
                    self.graph[neword].add(word)#存在多个出度，所以是append而不是赋值等号
                    self.graph[word].add(neword)
    def distance(self, word):
        dist = {}
        dist[word] = 0
        self.used.add(word)#由于该有向图存在环，可以互相变化，为了避难重复使用导致覆盖距离
        temp_list = [word]#为了BFS建立一个临时的表格
        while temp_list:
            word = temp_list.pop(0)#从最左开始取值，保证距离是从小到大
            for neighbor in self.graph[word]:
                if neighbor not in self.used:
                    self.used.add(neighbor)
                    temp_list.append(neighbor)
                    dist[neighbor] = dist[word] + 1
        return dist
    def findresult(self, word, end, dist, path):
        path.append(word)
        if word == end:
            self.result.append(copy.deepcopy(path))
            return
        for neighbor in self.graph[word]:
            if dist[neighbor] == dist[word] - 1: #如果距离相差为1，则录用
                self.findresult(neighbor, end, dist, path)
                path.pop()

单词接龙 II

原文：https://www.cnblogs.com/phinza/p/9864184.html

踩

(0)

评论一句话评论（0）

分享档案

更多>

2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)

单词接龙 II

单词接龙 II （来自lintecode：https://www.lintcode.com/problem/word-ladder-ii/?_from=ladder&&fromId=1）

样例

注意事项

1.所有单词具有相同的长度。

2.所有单词都只包含小写字母。

构造代码前的思路：

1.首先构造有向图，将start, end 以及dict里所有字符的可变化对象列在一个字典里。

2.计算每个字符距离终点的距离（BFS)

3.根据距离逐一添加进result (DFS)