目录

1. 问题描述

2. 方法一：广度优先搜索

2.1 思路

2.2 代码实现

3. 方法二：双向广度优先搜索

3.1 思路

3.2 代码

1. 问题描述

字典 wordList 中从单词 beginWord 和 endWord 的 转换序列 是一个按下述规格形成的序列 beginWord -> s1 -> s2 -> ... -> sk：

• 每一对相邻的单词只差一个字母。
•  对于 1 <= i <= k 时，每个 si 都在 wordList 中。注意， beginWord 不需要在 wordList 中。
• sk == endWord

给你两个单词 beginWord 和 endWord 和一个字典 wordList ，返回 从 beginWord 到 endWord 的 最短转换序列 中的 单词数目 。如果不存在这样的转换序列，返回 0 。

示例 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 <= beginWord.length <= 10
• endWord.length == beginWord.length
• 1 <= wordList.length <= 5000
• wordList[i].length == beginWord.length
• beginWord、endWord 和 wordList[i] 由小写英文字母组成
• beginWord != endWord
• wordList 中的所有字符串 互不相同

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/word-ladder
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 方法一：广度优先搜索

2.1 思路

        感觉这个问题leecode433(Leetcode0433. 最小基因变化(medium,BFS))就是换汤不换药嘛。

        另外跟leetcode752(Leetcode0752. 打开转盘锁(medium,BFS))也很相似，只不过leetcode752中是四位数的数码，本题换成换成单词了。可选项以wordlist的形式出现，而在leetcode752中是以一个规则加上一个forbidden列表相结合给出。

        采用和leetcode433相同的解决方案。为了方便以广度优先搜索的方式进行图搜索：先将beginWord与wordlist进行合并，然后以每个单词作为图中的一个节点间邻接列表。然后基于该邻接节点进行搜索。

        注意，如果endWord不在wordList中的话肯定无法转换。   

2.2 代码实现

        这个代码其实基本上就是在leetcode433的基础上稍微做了一些细微的修改而得。

import time
from typing import List
from collections import deque

class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        def diff_is_one(s1,s2)->bool:
            cnt=0
            for k in range(len(s1)):
                if s1[k]!=s2[k]:
                    cnt+=1
            return cnt==1
        
        # Construct adjacency list first
        endIdx  = -1
        wordList.insert(0, beginWord)
        for k,word in enumerate(wordList):
            if endWord==word:
                endIdx = k
        if endIdx<0:
            return 0
        
        adjlist = [ [] for k in range(len(wordList)) ]
        for k in range(len(wordList)):
            for j in range(k,len(wordList)):
                if diff_is_one(wordList[k], wordList[j]):
                    adjlist[k].append(j)
                    adjlist[j].append(k)
                    
        # print(bank,adjlist)
        q = deque([(0,0)])
        visited = set([0])
        while len(q)>0:
            node,layer = q.popleft()
            if node == endIdx:
                return layer+1
            for nxt in adjlist[node]:
                if nxt not in visited:
                    q.append((nxt,layer+1))
                    visited.add(nxt)
        return 0
    
if __name__ == "__main__":
    
    sln = Solution()
    
    beginWord = "hit"
    endWord = "cog"
    wordList = ["hot","dot","dog","lot","log","cog"]
    print(sln.ladderLength(beginWord, endWord, wordList))
        
    beginWord = "hit"
    endWord = "cog"
    wordList = ["hot","dot","dog","lot","log"]  
    print(sln.ladderLength(beginWord, endWord, wordList))

    with open('No0127-testcase.py','r') as f:
        exec(f.read())  
    tstart=time.time()    
    print(sln.ladderLength(beginWord, endWord, wordList))
    tstop=time.time()
    print('tcost = {0:4.2f}(sec)'.format(tstop-tstart))    

        提交超时。

        也不意外，毕竟leetcode是medium，这个是difficult。要是同一套代码直接提交成功了，怎么对得起difficult的级别。

3. 方法二：双向广度优先搜索

3.1 思路

        同时从两端出现进行广度优先搜索。

        中途如果一方从队列中弹出的节点出现在对方已访问列表中，双方搜索碰头，则表示搜索成功。

        与上面单端搜索不同的是，在已访问列表中也需要记忆layer信息，以便于碰头时计算两者走过的距离总和。

        因此visited改用dict来表示。

        双向广度优先搜索示意图如下（摘自力扣官解）：

3.2 代码

class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        def diff_is_one(s1,s2)->bool:
            cnt=0
            for k in range(len(s1)):
                if s1[k]!=s2[k]:
                    cnt+=1
            return cnt==1
        
        # Construct adjacency list first
        endIdx  = -1
        wordList.insert(0, beginWord)
        for k,word in enumerate(wordList):
            if endWord==word:
                endIdx = k
        if endIdx<0:
            return 0
        
        adjlist = [ [] for k in range(len(wordList)) ]
        for k in range(len(wordList)):
            for j in range(k,len(wordList)):
                if diff_is_one(wordList[k], wordList[j]):
                    adjlist[k].append(j)
                    adjlist[j].append(k)
                    
        # print(bank,adjlist)
        q1 = deque([(0,0)])
        visited1 = dict()
        visited1[0] = 0
        q2 = deque([(endIdx,0)])
        visited2 = dict()
        visited2[endIdx] = 0
        while len(q1)>0 or len(q2)>0:
            if len(q1)>0:
                node1,layer1 = q1.popleft()
                if node1 in visited2:
                    return layer1+visited2[node1]+1
                for nxt in adjlist[node1]:
                    if nxt not in visited1:
                        q1.append((nxt,layer1+1))
                        visited1[nxt]=layer1+1

            if len(q2)>0:            
                node2,layer2 = q2.popleft()
                if node2 in visited1:
                    return layer2+visited1[node2]+1
                for nxt in adjlist[node2]:
                    if nxt not in visited2:
                        q2.append((nxt,layer2+1))
                        visited2[nxt]=layer2+1
                    
        return 0

        三下两下码完双向广度优先搜索，以为这总可以了吧。不过拿刚才单向方案提交报超时的testcase一测，OMG！居然时间没有什么差异，只有10%左右的改善，显然这也是不行的。

        不明白为什么。容我再想一想。

        看了看官解，还要加上个优化建图的元素。。。感觉智商欠费脑力耗竭，改日再战。

        回到主目录：笨牛慢耕的Leetcode每日一解题解笔记(动态更新。。。)