《Leetcode》127. 单词接龙_leetcode单词接龙

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

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

如果不存在这样的转换序列，返回 0。
所有单词具有相同的长度。
所有单词只由小写字母组成。
字典中不存在重复的单词。
你可以假设 beginWord 和 endWord 是非空的，且二者不相同。

示例 1:

输入:
beginWord = "hit",
endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"]
 
输出: 5
 
解释: 一个最短转换序列是 "hit" -> "hot" -> "dot" -> "dog" -> "cog",
     返回它的长度 5。
 

示例 2:

输入:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]
 
输出: 0
 
解释: endWord "cog" 不在字典中，所以无法进行转换。

思路：

1、题目分析

题目要求每个单词只能做一个单词的变化，然后转换到endWord，求这个转换的最短距离。

2、解题分析

看到最短距离就想到了用BFS算法，再图的遍历过程中BFS算法算是一个比较经典的算法。能找出无向图从起点到终点的最短距离，所以尝试着把这个题目转换一下看能否转换成一个图。这个时候如过两个单词之间差一个变换，那就说明两个节点之间的距离就是1.这样就可以转换成图的遍历。但是存在一个问题，每个单词的变化都是有三种变化，那对应得wordlist里可能也有很多对应得word。为了简化这个情况把wordlist进行处理。把不相同得那个单词用*代替，然后把同类得放在一个value下面。处理完以后再把初始单词和初始长度添加到一个队列中去。在遍历队列。如果把每个单词得变化都在字典中去查找，如果查找到得结果等于endword，万事大吉，遍历结束。如果不是endword。那把节点添加到对列，并且长度加1.不过这块很容易出现环形结构，为了不让出现环形结构那么实现声明一个数组就存储访问过的节点。如果节点不在标记数组中才添加到队列，否则不添加到队列，继续遍历。

解题步骤：

①简化、处理wordlist

②遍历每个word的三种情况

③观察是否等于endword或者是否不在标记数组中

④最后返回长度

先放代码，然后画图梳理：

class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        #如果这个endword不在wordlist中 返回结果就是0
        if endWord not in wordList:
            return 0
        
        #声明队列和数组以及单词长度
        queue  = collections.deque()
        dic = collections.defaultdict(list)
        L = len(beginWord)
        
        #处理列表中的单词,将他们返回成统一格式的字符
        for item in wordList:
            for i in range(L):
                dic[item[:i]+"*"+item[i+1:]].append(item)
        print(dic)
        #添加一个元组到队列中,单词和当前层数,也就是距离
        queue.append((beginWord,1))
        
        #标记数组,防止出现环
        visit = {beginWord:True}
        
        while queue:
            cur,level = queue.popleft()
            for i in range(L):
                current = cur[:i]+'*'+cur[i+1:]
 
                #查找当前的元素在不在字典的value中
                for current in dic[current]:
                    if current==endWord:
                        return level+1
                    #如果不再标记数组中，添加进去然后更新队列
                    if current not in visit:
                        visit[current]=True
                        queue.append((current,level+1))
        return 0

画图：
 

总结：我以为我明白了BFS，其实我还是个弟弟。不会抽象问题，然后用数据结构的思想去解决。