单词接龙

这个题解采用了双向广度优先搜索（BFS）的思路来解决单词接龙问题。首先，将所有单词存储在一个字典中，并为每个单词分配一个唯一的ID。然后，构建一个无向图，其中每个节点表示一个单词，如果两个单词只相差一个字母，则在它们之间添加一条边。接下来，同时从起点单词和终点单词开始进行BFS，每次搜索一层节点。如果在某一层发现起点单词的BFS和终点单词的BFS相遇，则找到了最短转换序列，返回序列的长度。如果其中一个BFS搜索完了所有节点而没有相遇，则说明不存在转换序列，返回0。

时间复杂度: O(N * L^2)

空间复杂度: O(N * L)

```python
class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        wordId = {}
        edges = collections.defaultdict(list)
        nodeNum = 0
        
        # 将单词加入到字典中并分配唯一ID
        def addWord(word):
            nonlocal nodeNum
            if word not in wordId:
                wordId[word] = nodeNum
                nodeNum += 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]
                edges[id1].append(id2)
                edges[id2].append(id1)
                chars[i] = tmp

        # 将所有单词加入无向图中
        for word in wordList:
            addEdge(word)
        addEdge(beginWord)

        # 如果endWord不在字典中，则无法进行转换
        if endWord not in wordId:
            return 0
        
        # 分别从beginWord和endWord开始进行双向BFS
        beginId = wordId[beginWord]
        queBegin = collections.deque([beginId])
        disBegin = [float('inf')] * nodeNum
        disBegin[beginId] = 0

        endId = wordId[endWord]
        queEnd = collections.deque([endId])
        disEnd = [float('inf')] * nodeNum
        disEnd[endId] = 0

        # 双向BFS搜索
        while queBegin or queEnd:
            nodeBeginNum = len(queBegin)
            for _ in range(nodeBeginNum):
                nodeIdBegin = queBegin.popleft()
                if disEnd[nodeIdBegin] != float('inf'):
                    return (disBegin[nodeIdBegin] + disEnd[nodeIdBegin]) // 2 + 1
                for it in edges[nodeIdBegin]:
                    if disBegin[it] == float('inf'):
                        queBegin.append(it)
                        disBegin[it] = disBegin[nodeIdBegin] + 1
            nodeEndNum = len(queEnd)
            for _ in range(nodeEndNum):
                nodeEndId = queEnd.popleft()
                if disBegin[nodeEndId] != float('inf'):
                    return (disBegin[nodeEndId] + disEnd[nodeEndId]) // 2 + 1
                for it in edges[nodeEndId]:
                    if disEnd[it] == float('inf'):
                        queEnd.append(it)
                        disEnd[it] = disEnd[nodeEndId] + 1
        
        # 如果两个BFS都搜索完了所有节点仍未相遇，则不存在转换序列
        return 0            
```