当前位置:   article > 正文

LeetCode 第127题-单词接龙-Python_leetcode 127 python

leetcode 127 python

题目

给定两个单词(beginWord 和 endWord)和一个字典,找到从 beginWord 到 endWord 的最短转换序列的长度。转换需遵循如下规则:

  1. 每次转换只能改变一个字母。
  2. 转换过程中的中间单词必须是字典中的单词。

说明:

  • 不存在这样的转换序列,返回 0。
  • 所有单词具有相同的长度。
  • 所有单词只由小写字母组成。
  • 字典中不存在重复的单词。
  • 你可以假设 beginWord 和 endWord 是非空的,且二者不相同。
输入:
beginWord = "hit",
endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"]

输出: 5

解释: 一个最短转换序列是 "hit" -> "hot" -> "dot" -> "dog" -> "cog",
     返回它的长度 5。

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10

官方题解:广度优先搜索 + 优化建图1

整体思路:求最短序列长度==>想到图模型==>想到广度优先搜索

构建图思路:

  1. 如何选择节点? 将单词看做节点
  2. 如何选择相邻节点? 单词仅相差一个字母看做相邻节点
  3. 如何选择构造图? 构建无向图,将相邻节点互相连接

效果图示:Alt

算法

方法一代码解释:

建图阶段

  1. 创节点:为了方便用单词表示节点,为单词(beginWord, WordList)分配编号,使用哈希表(字典)实现一个单词到编号的映射 (“word”: id)
  2. 直接建图的问题:枚举每一对单词的组合,判断它们是否恰好相差一个字符效率低,故使用优化建图,即使用虚拟节点
  3. 虚拟节点:
虚拟节点。对于单词 hit,我们创建三个虚拟节点 *it、h*t、hi*,
并让 hit 向这三个虚拟节点分别连一条边即可。如果一个单词能够转化为 hit,
那么该单词必然会连接到这三个虚拟节点之一。对于每一个单词,
我们枚举它连接到的虚拟节点,
把该单词对应的 id 与这些虚拟节点对应的 id 相连即可。
  • 1
  • 2
  • 3
  • 4
  • 5

举例解释:对于如:“hit"与“hot”这种相差一个字符的单词,共同连接“hit”所指向的三个边之一的虚拟节点"h*t”,由此方法,将所有仅差一个字母的单词节点相互连接。
注意:因为添加了虚拟节点,所以我们得到的距离为实际最短路径长度的两倍。 在最终结果需要返回当前距离一般减一的结果

广度优先遍历

本题中,使用双向队列实现广度优先遍历:

  1. dis = [float(“inf”)] * 总节点数,初试定义beginWord到每个节点的距离为空
  2. 插入beginWord节点,到队列。若为beginWord节点的相邻节点,将dis中此节点的值改为“1”,将结点加入队列。
  3. 重复进行广度优先遍历,直到找到endWord节点。
    实例图2
    Alt

代码

import collections
from collections import defaultdict
class Solution:
    def ladderLength( beginWord, endWord, wordList) -> int:
        def addWord(word: str):
            # 计数结点总数
            if word not in wordId:
                nonlocal nodeNum    # nonlocal声明的变量不是局部变量,也不是全局变量,而是外部嵌套函数内的变量。表示在一个总def中做同一变量
                # print(nodeNum)
                wordId[word] = nodeNum
                # print(word)    # word 表示单词
                nodeNum += 1
                
        
        def addEdge(word: str):
            # 创建图
            addWord(word)
            id1 = wordId[word]    # id2是真实结点的结点编号
            chars = list(word)
            for i in range(len(chars)):
                tmp = chars[i]
                chars[i] = "*"
                newWord = "".join(chars)    # 组成新的单词
                addWord(newWord)    # 为虚拟单词建立虚拟结点
                id2 = wordId[newWord]    # id2是虚拟结点的结点编号
                edge[id1].append(id2)    # edge是字典,将此虚拟结点的词连接真实结点中
                # print(edge)
                edge[id2].append(id1)    # 双向连接,形成双向图
                chars[i] = tmp    # 恢复单词

        wordId = dict()
        edge = collections.defaultdict(list)    # Python内建字典类(dict)的一个子类 (class list)表示边 
        nodeNum = 0
        
        # --------------------------------------------------------
        for word in wordList:
            addEdge(word)    # 对单词字典列表中的单词插入边与结点
        
        addEdge(beginWord)    # 将首个单词加入图中与对应虚拟结点加入图中
        # 创建图完毕
        # --------------------------------------------------------
        
        # 当给出结尾词不在字典中,必无最短路径
        if endWord not in wordId:
            return 0
        
        dis = [float("inf")] * nodeNum
        beginId, endId = wordId[beginWord], wordId[endWord]    # 获得开始结束单词的id
        # print(beginId, endId)
        dis[beginId] = 0    # 将距离中的beginId设置为 0

        que = collections.deque([beginId])    # 实现双端队列
        while que:
            x = que.popleft()
            if x == endId:
                return dis[endId] // 2 + 1
            for it in edge[x]:
                # 从开始结点开始寻找,实现广度优先遍历
                if dis[it] == float("inf"):
                    dis[it] = dis[x] + 1
                    print(it,dis[it])
                    que.append(it)
        
        return 0

  • 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
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65

  1. https://leetcode-cn.com/problems/word-ladder/solution/dan-ci-jie-long-by-leetcode-solution/ ↩︎

  2. https://leetcode-cn.com/problems/word-ladder/solution/bfsjie-jue-yi-quan-yi-quan-wang-wai-kuo-san-by-sdw/ ↩︎

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/从前慢现在也慢/article/detail/144304
推荐阅读
相关标签
  

闽ICP备14008679号