127. 单词接龙

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

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

说明：

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

示例1：

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

示例2：

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

方法一：广度优先搜素+优化建图

思路:

本题要求的是最短转换序列的长度。广度优先搜索。抽象为图的模型。

每个单词抽象为一个点，如果两个单词可以只改变一个字母进行转换，那么说明它们之间有一条双向边，因此我们只需要把满足转换条件的点相连，就形成了一张图。
基于该图，我们以beginWord为图的起点，以endWord为终点进行广度优先搜索，寻找beginWord和endWord的最短路径。

具体地，我们可以创建虚拟节点。对于单词hit，我们创建三个虚拟节*it、h*t、hi*，并让hit向这三个虚拟节点分别连一条边即可。如果一个单词能够转换为hit，那么该单词必然会连接到这三个虚拟节点之一。对于每一个单词，我们枚举它连接到的虚拟节点，把该单词对应的id与这些虚拟节点对应的id相连即可。

最后我们将起点加入队列开始广度优先搜索，当搜索到终点时，我们就找到了最短路径的长度。注意因为添加了虚拟节点，我们得到的距离为实际最短路径长度的两倍。同时我们并未计算起点对答案的贡献，所以我们应当返回距离的一半加一的结果。

代码:

import collections
class Solution:
    def ladderLength(self, beginWord, endWord,wordList):
        def addWord(word):
            if word not in wordId:
                nonlocal wordnum
                wordId[word] = wordnum
                wordnum += 1
        def addEdge(word):
            addWord(word)
            id1 = wordId[word]
            chars = list(word)
            for i in range(len(chars)):
                tmp = chars[i]
                chars[i] = '*'
                newword = ''.join(chars)
                addWord(newword)
                id2 = wordId[newword]
                edge[id1].append(id2)
                edge[id2].append(id1)
                chars[i] = tmp
        
        wordId = dict()
        edge = collections.defaultdict(list)
        wordnum = 0
        for word in wordList:
            addEdge(word)
        addEdge(beginWord)
        dis = [float("inf")] * wordnum
        if endWord not in wordId:
            return 0
        beginId, endId  = wordId[beginWord], wordId[endWord]
        dis[beginId] = 0
        que = collections.deque([beginId])
        while que:
            x = que.popleft()
            if x == endId:
                return dis[endId] // 2 + 1
            for nextnode in edge[x]:
                if dis[nextnode] == float("inf"):
                    dis[nextnode] = dis[x] + 1
                    que.append(nextnode)
        return 0

复杂度分析:

时间复杂度：$O(N \times C^2)$？？？？。其中$N$为wordList的长度，$C$为列表中单词的平均长度。
- 建图过程中，对于每一个单词，我们需要枚举它连接到的所有虚拟节点，时间复杂度为$O(C)$，将这些单词加入到哈希表中，时间复杂度为$O(N \times C)$，因此总时间复杂度为$O(N \times C)$。
- 广度优先搜索的时间复杂度最坏情况下是$O(N \times C)$。
空间复杂度：$O(N \times C^2)$。其中$N$为wordList的长度，$C$为列表中单词的平均长度。哈希表中包含$O(N \times C)$个节点，每个节点占用空间$O(C)$，因此总的空间复杂度为$O(N \times C)$。

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

思路:

根据给定字典构造的图可能会很大，而广度优先搜索的搜索空间大小依赖于每层节点的分支数量。假如每个节点的分支数量相同，搜索空间会随着层数的增长指数级的增加。

如果使用两个同时进行的广搜可以有效地减少搜索空间。一边从beginWord开始，另一边从endWord开始。我们每次从两个各扩展一层节点，当发现某一时刻两边都访问过同一顶点时就停止搜索。这就是双向广度优先搜索，它可以可观地减少搜索空间，从而提高代码运行效率。

代码:

class Solution:
    def ladderLength(self, beginWord, endWord, wordList):
        def addWord(word):
            if word not in wordId:
                nonlocal wordnum
                wordId[word] = wordnum
                wordnum += 1
        def addEdge(word):
            addWord(word)
            id1 = wordId[word]
            chars = list(word)
            for i in range(len(chars)):
                tmp = chars[i]
                chars[i] = '*'
                newword = ''.join(chars)
                addWord(newword)
                id2 = wordId[newword]
                edge[id1].append(id2)
                edge[id2].append(id1)
                chars[i] = tmp
        wordnum = 0
        wordId = dict()
        edge = collections.defaultdict(list)
        for word in wordList:
            addEdge(word)
        addEdge(beginWord)
        if endWord not in wordId:
            return 0
        beginId, endId = wordId[beginWord], wordId[endWord]
        quebegin = collections.deque([beginId])
        disbegin = [float('inf')] * wordnum
        disbegin[beginId] = 0
        queend = collections.deque([endId])
        disend = [float('inf')] * wordnum
        disend[endId] = 0
        while quebegin or queend:
            quebeginsize = len(quebegin)
            for _ in range(quebeginsize):
                nodebegin = quebegin.popleft()
                if disend[nodebegin] != float('inf'):
                    return (disbegin[nodebegin] + disend[nodebegin]) // 2 + 1
                for nextnode in edge[nodebegin]:
                    if disbegin[nextnode] == float('inf'):
                        disbegin[nextnode] = disbegin[nodebegin] + 1
                        quebegin.append(nextnode)
            queendsize = len(queend)
            for _ in range(queendsize):
                nodeend = queend.popleft()
                if disbegin[nodeend] != float('inf'):
                    return (disbegin[nodeend] + disend[nodeend]) // 2 + 1
                for nextnode in edge[nodeend]:
                    if disend[nextnode] == float('inf'):
                        disend[nextnode] = disend[nodeend] + 1
                        queend.append(nextnode)
        return 0

复杂度分析:

时间复杂度：$O(N \times C^2)$。其中$N$为wordList的长度，$C$为列表中单词的平均长度。
- 建图过程中，对于每一个单词，我们需要枚举它连接到的所有虚拟节点，时间复杂度为$O(C)$，将这些单词加入哈希表中，时间复杂度为$O(N \times C)$，因此总时间复杂度为$O(N \times C)$。
- 双向广度优先搜索的时间复杂度最坏情况下是$O(N \times C)$，因此总时间复杂度为$O(N \times C^2)$。
空间复杂度：$O(N \times C^2)$。其中$N$为wordList的长度，$C$为列表中单词的平均长度，哈希表中包含$O(N \times C)$个节点，每个节点占用空间$O(C)$。因此总的空间复杂度为$O(N \times C^2)$。