从单词接龙到图论：BFS、双向BFS与A*算法详解

1. 问题引入：从“单词接龙”到“无权图最短路径”

最近在LeetCode上又刷到了第127题“单词接龙”，这道题可以说是图论搜索算法的经典面试题，也是很多朋友在准备算法面试时的“拦路虎”。题目本身描述很简单：给你一个起始单词、一个结束单词和一个单词列表，每次只能改变单词中的一个字母，并且改变后的新单词必须在给定的列表中，问你从起始单词到结束单词的最短转换序列长度是多少。

乍一看，这像是一个字符串操作题，但如果你真的去尝试用暴力枚举或者简单的递归回溯，很快就会遇到性能瓶颈。我第一次做这道题时，就掉进了这个坑里。当时我试图用DFS去搜索所有可能的转换路径，结果在单词列表稍大一点（比如几百个）的时候，程序就直接超时了。后来才明白，这本质上是一个单源无权最短路问题。

为什么这么说？我们可以把每个单词看作图中的一个“节点”。如果两个单词之间只差一个字母（比如“hit”和“hot”），那么它们之间就存在一条“边”。我们的目标，就是从起始节点（如“hit”）出发，找到一条最短的路径，到达目标节点（如“cog”）。因为每条边的“权重”都是1（转换一次算一步），所以这是一个典型的无权图。在无权图中寻找单源最短路径，最经典、最高效的算法就是广度优先搜索。

这道题的魅力在于，它不仅仅考察你是否知道BFS，更考察你能否对问题进行准确的数学建模，以及能否在基础BFS之上进行优化。从最朴素的BFS，到减少搜索空间的双向BFS，再到引入启发式函数的A-Star (A*)搜索，每一步优化都对应着对问题理解的加深和对算法效率的极致追求。接下来，我们就从建模开始，一步步拆解这道题，并深入探讨各种解法的实现细节与性能差异。

2. 核心建模：如何将单词列表转化为一张图？

解决任何图论问题的第一步，都是建立正确的模型。对于“单词接龙”，建模的质量直接决定了后续算法实现的复杂度和效率。

2.1 节点与边的定义

最直观的想法是：节点就是单词本身。例如，单词列表[“hot”,”dot”,”dog”,”lot”,”log”,”cog”]中的每一个字符串，都是一个独立的节点。

那么，边如何定义？题目规则是“每次改变一个字母”。因此，对于任意两个节点（单词）A和B，如果它们长度相同，并且有且仅有一个对应位置的字母不同，那么A和B之间就存在一条无向边。例如，“hot”和“dot”仅第一个字母不同，它们相连；“dot”和“dog”仅第三个字母不同，它们也相连。

2.2 邻接关系的构建：两种策略与性能抉择

知道了定义，我们如何在代码中高效地构建出这张图的邻接关系呢？这里有两种主流策略，其性能差异巨大。

策略一：两两比较法（暴力法）最直接的方法是双重循环遍历单词列表，对每一对单词word[i]和word[j]，逐个字母比较，判断是否只差一个字母。如果是，则将它们互相加入对方的邻接表。

def build_graph_naive(wordList): graph = {word: [] for word in wordList} n = len(wordList) for i in range(n): for j in range(i+1, n): if is_one_letter_diff(wordList[i], wordList[j]): graph[wordList[i]].append(wordList[j]) graph[wordList[j]].append(wordList[i]) return graph def is_one_letter_diff(a, b): diff_count = 0 for ch_a, ch_b in zip(a, b): if ch_a != ch_b: diff_count += 1 if diff_count > 1: return False return diff_count == 1

这种方法的时间复杂度是 O(N^2 * L)，其中N是单词数量，L是单词长度。当N很大时（比如达到5000），这个开销是无法接受的。这也是很多初学者代码超时的第一个原因。

策略二：虚拟节点法（高效通用法）这是一种更巧妙、更高效的方法，也是解决此类问题的标准建模技巧。其核心思想是引入“虚拟节点”。

对于单词”hot”，我们为它的每一个位置创建一个“模糊”模式：

• 模式”*ot”：表示第一位是任意字母，后两位是”ot”的单词。
• 模式”h*t”：表示第二位是任意字母。
• 模式”ho*”：表示第三位是任意字母。

那么，所有能与”hot”直接转换的单词，比如”dot”，必然也属于模式”*ot”。同理，”hit”属于模式”*it”，但”hot”不属于”*it”，所以它们不相连。

这样，我们构建的图包含两类节点：原始单词节点和虚拟模式节点。每个原始单词都通过边连接到它的所有模式节点。如果两个原始单词共享同一个模式节点，那么它们之间就通过这个模式节点间接相连，且距离为2（原始A -> 模式 -> 原始B）。在BFS中，我们关心的是原始节点之间的转换步数，因此从A到B的路径长度需要除以2（或者直接在BFS计数时进行相应处理）。

构建邻接关系的代码变得高效：

from collections import defaultdict def build_graph_pattern(wordList): # 邻接表：记录每个单词的直接邻居（其他原始单词） graph = defaultdict(list) # 模式字典：记录每个模式下对应的所有单词 pattern_dict = defaultdict(list) for word in wordList: for i in range(len(word)): # 构造模式：将第i位替换为通配符’*‘ pattern = word[:i] + ‘*‘ + word[i+1:] # 当前单词关联到这个模式 pattern_dict[pattern].append(word) # 基于模式字典构建原始单词间的邻接关系 for pattern, words in pattern_dict.items(): # 属于同一模式的所有单词，彼此之间都只差一个字母 for i in range(len(words)): for j in range(i+1, len(words)): graph[words[i]].append(words[j]) graph[words[j]].append(words[i]) return graph

这种方法的时间复杂度主要是 O(N * L)。构建模式字典需要遍历每个单词的每个位置（O(N*L)）。构建邻接表时，最坏情况下每个模式包含所有单词（极端情况），但实际中同一个模式下的单词数量有限，因此整体效率远高于 O(N^2)。这是解决本题必须掌握的建模方法。

注意：在实际BFS实现中，我们甚至可以省略显式构建graph这一步。在BFS的每一步，当我们访问一个单词current_word时，我们实时生成它的所有可能模式，然后从预先构建好的pattern_dict中取出共享这些模式的所有单词，这些单词就是current_word的未访问邻居。这种方式更节省内存，是更常见的写法。

2.3 将问题抽象为算法问题

通过以上建模，我们成功地将一个字符串转换问题，抽象成了一个标准的图论问题：

• 图：节点是单词，边表示可一次转换的关系。
• 问题：在无权图中，求从起点beginWord到终点endWord的最短路径长度（边数）。
• 输出：最短路径长度。如果终点不可达，返回0。

模型建立好了，接下来就可以请出我们的第一员大将：广度优先搜索。

3. 基础解法：广度优先搜索的标准化实现

BFS是解决无权图最短路径问题的“银弹”。它的核心思想是“一层一层”地探索。从起点开始，先访问所有距离为1的邻居，再访问所有距离为2的邻居（即邻居的邻居），以此类推。当第一次访问到终点时，当前的层数就是最短路径长度。

3.1 BFS算法框架与队列的使用

一个标准的BFS实现需要以下组件：

1. 队列：用于存储待访问的节点，并保证“先进先出”的顺序，从而实现按层遍历。
2. 已访问集合：记录已经进入过队列的节点，避免重复访问和死循环。
3. 距离记录：记录每个节点到起点的距离（层数）。

以下是针对本题的BFS实现步骤：

步骤1：预处理与初始化首先，将单词列表转换为集合，便于 O(1) 时间的查找。同时，检查终点是否在列表中，如果不在，直接返回0。 将起点beginWord加入队列和已访问集合。此时，起点距离为1（转换序列包含起点本身）。

步骤2：BFS循环主体当队列不为空时，循环执行：

1. 获取当前层的节点数量level_size。这一步是关键，它帮助我们区分队列中的节点属于哪一层。
2. 循环level_size次，每次从队列中取出一个节点current_word。
3. 生成current_word的所有可能模式（虚拟节点）。
4. 对于每个模式，从pattern_dict中找到所有与之匹配的单词（即邻居）。
5. 遍历这些邻居单词：
   • 如果邻居是endWord，说明找到了终点，返回当前距离steps + 1（因为当前steps是走到current_word的步数，再走一步到终点）。
   • 如果邻居未被访问过，则将其标记为已访问，并加入队列。
6. 当前层所有节点处理完毕后，将steps加1，进入下一层。

步骤3：循环结束如果BFS循环结束（队列为空）仍未找到endWord，说明终点不可达，返回0。

3.2 代码实现与细节剖析

from collections import deque, defaultdict def ladderLength(beginWord, endWord, wordList): # 1. 预处理：将单词列表转为集合，并构建模式字典 word_set = set(wordList) if endWord not in word_set: return 0 # 为了方便，将beginWord也加入集合，以便构建其模式 word_set.add(beginWord) # 构建模式字典 pattern_dict = defaultdict(list) for word in word_set: for i in range(len(word)): pattern = word[:i] + ‘*‘ + word[i+1:] pattern_dict[pattern].append(word) # 2. BFS初始化 queue = deque([beginWord]) visited = {beginWord} steps = 1 # 起点算第一步 # 3. BFS循环 while queue: level_size = len(queue) for _ in range(level_size): current_word = queue.popleft() # 生成当前单词的所有模式，并查找邻居 for i in range(len(current_word)): pattern = current_word[:i] + ‘*‘ + current_word[i+1:] for neighbor in pattern_dict[pattern]: if neighbor == endWord: return steps + 1 if neighbor not in visited: visited.add(neighbor) queue.append(neighbor) steps += 1 return 0

几个关键细节：

• steps的初始值：这里设为1，代表序列包含起点。当找到endWord时，返回steps + 1，意味着序列包含了从起点到终点的所有节点。另一种常见写法是steps初始为0，找到终点时返回steps + 1，两者等价，但需注意边界条件。
• 已访问集合的时机：必须在节点入队时就将其加入visited集合，而不是出队时。如果出队时才标记，可能导致同一个节点被多次加入队列，造成不必要的冗余计算和内存消耗。
• 模式字典的包含范围：构建pattern_dict时，必须将beginWord也包含进去，否则无法找到从起点出发的边。

3.3 复杂度分析与适用场景

• 时间复杂度：O(N * L^2)。其中N是单词数量。对于每个出队节点，我们需要生成L个模式（O(L)），每个模式可能对应多个邻居，但每个单词最多被访问一次，且每个单词有L个模式。更精确的分析是，每条边（单词-模式-单词）最多被遍历两次。在构建模式字典时，每个单词的每个模式都被处理一次，总体是O(NL)。BFS过程中，每个节点（单词）出队一次，处理其L个模式，每个模式下的邻居列表遍历总和与边的数量成正比，最坏情况下也是O(NL)。因此综合是O(NL)级别，考虑到字符串比较等操作，常表述为O(NL^2)。
• 空间复杂度：O(N * L)。主要用于存储模式字典pattern_dict（每个单词有L个模式入口）和BFS队列、已访问集合。

适用场景：朴素的BFS实现清晰、可靠，在单词列表规模中等（几千以内）时表现良好，是面试中最容易理解和写对的解法。然而，当搜索空间很大，或者起点和终点分别位于“图”的两端时，BFS会像涟漪一样从起点向外均匀扩散，直到触及终点，这可能会探索大量不必要的节点。接下来，我们将看到如何优化这个扩散过程。

4. 进阶优化一：双向广度优先搜索

单向BFS是从起点向终点进行“地毯式”搜索。想象一下，如果起点和终点相距很远，这个搜索的“涟漪”需要扩散很多层才能相遇，搜索范围是一个以起点为圆心的大圆。

双向BFS的核心思想是从起点和终点同时开始BFS。两个搜索的“涟漪”分别从起点和终点向外扩散，当它们在中间某个节点相遇时，路径就找到了。这样，搜索范围变成了两个相对较小的圆，它们相遇时覆盖的总面积远小于一个大圆，从而显著减少探索的节点数量。

4.1 双向BFS的工作原理与实现框架

实现双向BFS，我们需要维护两套BFS的“前线”：queue_begin（从起点出发）、queue_end（从终点出发），以及对应的已访问集合visited_begin、visited_end。此外，我们还需要一个从节点到距离的映射distance_begin、distance_end，但在此问题中，由于我们只关心最短路径长度，且使用层序遍历，可以用当前扩展的层来代表距离。

算法步骤如下：

1. 初始化：将起点加入queue_begin和visited_begin，将终点加入queue_end和visited_end。如果起点和终点相同，返回1。
2. 交替扩展：在每一轮中，我们选择当前节点数较少的那一端进行扩展（这是一种优化，优先扩展规模小的队列，有助于更快相遇）。这能平衡两边的搜索进度。
3. 扩展过程：从选中的队列中取出当前层的所有节点。对于每个节点，生成其所有邻居。
   • 如果某个邻居已经被另一端访问过（即在另一端的visited集合中），那么我们就找到了连接两端的路径。总路径长度 = 从起点到当前节点的距离 + 从终点到该邻居节点的距离 + 1。
   • 否则，如果该邻居未被当前端访问过，则将其加入当前端的队列和已访问集合。
4. 终止条件：当某一端的队列为空时，说明该方向已无法继续前进，而两端仍未相遇，则终点不可达。

4.2 代码实现与关键技巧

from collections import deque, defaultdict def ladderLength_bi_bfs(beginWord, endWord, wordList): word_set = set(wordList) if endWord not in word_set: return 0 if beginWord == endWord: return 1 word_set.add(beginWord) # 构建模式字典 pattern_dict = defaultdict(list) for word in word_set: for i in range(len(word)): pattern = word[:i] + ‘*‘ + word[i+1:] pattern_dict[pattern].append(word) # 双向BFS初始化 queue_begin = deque([beginWord]) queue_end = deque([endWord]) visited_begin = {beginWord} visited_end = {endWord} steps_begin = 1 # 从起点开始的步数 steps_end = 1 # 从终点开始的步数 (反向) while queue_begin and queue_end: # 优化：总是扩展节点数较少的那一端 if len(queue_begin) > len(queue_end): queue_begin, queue_end = queue_end, queue_begin visited_begin, visited_end = visited_end, visited_begin steps_begin, steps_end = steps_end, steps_begin level_size = len(queue_begin) for _ in range(level_size): current_word = queue_begin.popleft() for i in range(len(current_word)): pattern = current_word[:i] + ‘*‘ + current_word[i+1:] for neighbor in pattern_dict[pattern]: # 关键判断：如果邻居已被另一端访问过，则相遇 if neighbor in visited_end: return steps_begin + steps_end if neighbor not in visited_begin: visited_begin.add(neighbor) queue_begin.append(neighbor) steps_begin += 1 return 0

实现中的关键点：

• “相遇”的判断：在扩展queue_begin中的节点current_word时，我们检查它的邻居neighbor是否在visited_end中。如果在，说明从终点出发的BFS已经访问过这个节点。此时，从起点到current_word的距离是steps_begin，从终点到neighbor的距离是steps_end（注意，steps_end记录的是从终点反向搜索的层数）。那么总路径就是steps_begin + steps_end。为什么不是steps_begin + steps_end + 1？因为current_word到neighbor是一条边，而neighbor已被对端访问，这条边被计算了两次（两端各一次），所以直接相加即可。
• 队列与集合的交换：代码中通过交换变量来实现“总是扩展较小队列”的优化。这需要同时交换队列、已访问集合和步数计数器，逻辑上要小心处理。
• 步数计数：steps_begin和steps_end分别记录从起点和终点开始的BFS当前所在的层数（距离）。它们初始值都是1，代表包含起点或终点本身。

4.3 性能对比与适用性分析

双向BFS在最坏情况下的时间复杂度理论上仍然是 O(N * L^2)，因为最坏情况下它仍然需要访问所有节点。但是，在平均情况和许多实际情况下，它能极大地减少实际访问的节点数量，从而提升运行速度。

我们可以做一个简单的思想实验：假设图是一个比较均匀的连通图，从起点到终点的最短路径长度为D。单向BFS需要探索大约半径为D的“球”内的所有节点。双向BFS则从两端探索，每个方向只需要探索半径大约为D/2的“球”。在节点密度均匀的情况下，后者的搜索空间大约是前者的平方关系，即从 O(k^D) 级别降到 O(k^{D/2}) 级别（k是平均节点度数），这是一个指数级的优化。

适用场景：当已知起点和终点，且图规模较大、最短路径较长时，双向BFS的优势非常明显。在LeetCode本题的测试用例中，双向BFS通常比单向BFS快数倍。它是在面试中展示算法优化能力的加分项。

然而，双向BFS也有其局限性：它需要明确知道起点和终点。对于一些搜索目标不明确（比如寻找任意满足条件的节点）的问题，它就无法使用。此外，代码实现比单向BFS稍复杂，需要注意交换逻辑和相遇判断的细节。

5. 进阶优化二：A-Star搜索算法

如果说BFS是“盲目”地逐层探索，那么A-Star搜索则是一种“启发式”的智能搜索。它尝试朝着“最有希望”的方向前进，从而可能更快地找到目标。

5.1 A-Star算法核心：估价函数与优先级队列

A-Star算法为每个待探索的节点计算一个估价函数：f(n) = g(n) + h(n)。

• g(n)：从起点到节点n的实际代价。在本题中，就是BFS中的步数（层数）。
• h(n)：从节点n到终点的预估代价，即启发函数。h(n)必须满足可采纳性，即它永远不会高估从n到终点的实际代价。在本题中，由于每次只能改变一个字母，两个单词之间的实际最短转换次数至少等于它们不同字母的个数。因此，一个很自然的启发函数就是：h(n) = 当前单词与终点单词不同字母的个数。

A-Star使用一个优先级队列（通常是最小堆）来管理待探索的节点。优先级由f(n)决定，f(n)值小的节点优先级高，优先被取出探索。这样，算法会倾向于探索那些综合代价（已走距离+预估剩余距离）最小的节点，理论上可以更快地接近终点。

5.2 针对本题的A-Star实现细节

在本题中应用A-Star，需要注意以下几点：

1. 状态表示：每个状态就是当前单词。
2. 代价g(n)：从beginWord到当前单词n已经转换的次数。
3. 启发函数h(n)：h(n) = word_diff(n, endWord)，即两个单词对应位置字母不同的数量。
4. 数据结构：
   • open_set：一个优先级队列，存储待探索的节点，按f(n)排序。
   • g_score：字典，记录从起点到每个节点的最短已知距离g(n)。
   • came_from：字典，记录每个节点的前驱节点，用于最终重构路径（本题不需要路径长度，但保留此结构有助于理解）。

算法过程：

1. 初始化open_set，加入起点，其f_score = h(beginWord)。
2. 初始化g_score[beginWord] = 0。
3. 循环直到open_set为空： a. 从open_set中取出f_score最小的节点current。 b. 如果current == endWord，返回g_score[current] + 1。 c. 遍历current的所有邻居neighbor。 d. 计算从起点经过current到neighbor的tentative_g_score = g_score[current] + 1。 e. 如果tentative_g_score < g_score.get(neighbor, float(‘inf‘))，说明找到了一条到neighbor的更短路径。 - 更新g_score[neighbor] = tentative_g_score。 - 计算f_score = tentative_g_score + h(neighbor)。 - 将neighbor加入open_set（如果已在集合中，需要更新其优先级）。

5.3 代码示例与复杂度讨论

import heapq def ladderLength_a_star(beginWord, endWord, wordList): word_set = set(wordList) if endWord not in word_set: return 0 word_set.add(beginWord) # 启发函数：汉明距离 def heuristic(word, target): return sum(1 for a, b in zip(word, target) if a != b) # 构建模式字典 pattern_dict = defaultdict(list) for word in word_set: for i in range(len(word)): pattern = word[:i] + ‘*‘ + word[i+1:] pattern_dict[pattern].append(word) # A-Star 初始化 open_set = [] heapq.heappush(open_set, (heuristic(beginWord, endWord), beginWord)) g_score = {beginWord: 0} while open_set: _, current = heapq.heappop(open_set) current_g = g_score[current] if current == endWord: return current_g + 1 for i in range(len(current)): pattern = current[:i] + ‘*‘ + current[i+1:] for neighbor in pattern_dict[pattern]: tentative_g = current_g + 1 if tentative_g < g_score.get(neighbor, float(‘inf‘)): # 找到了到neighbor的更优路径 g_score[neighbor] = tentative_g f_score = tentative_g + heuristic(neighbor, endWord) heapq.heappush(open_set, (f_score, neighbor)) return 0

复杂度与性能分析：

• 时间复杂度：最坏情况下，A-Star仍然需要访问所有节点，复杂度为 O(N log N)，因为优先级队列的插入和弹出操作是 O(log N)。这个log因子使得在最坏情况下，A-Star可能比朴素的BFS还要慢。
• 空间复杂度：与BFS类似，需要存储g_score字典和优先级队列。

A-Star的优势与陷阱：

• 优势：当启发函数h(n)设计得很好，能有效指导搜索方向时，A-Star可以极大地减少探索的节点数，比BFS快得多。在本题中，h(n)使用汉明距离，这是一个可采纳的启发函数（因为每次只能改一个字母，实际步数不可能比不同字母数少），但它的“信息量”有时不够大，尤其是在单词长度较短时。
• 陷阱：
  1. 启发函数的质量：如果h(n)恒为0，A-Star就退化成了Dijkstra算法（在无权图中等同于BFS）。如果h(n)高估了实际代价，A-Star可能找不到最优解。本题的汉明距离是安全的，但未必总是高效。
  2. 优先级队列的开销：维护堆结构有额外开销。在本题这种边权为1的图中，BFS的普通队列操作是O(1)，而A-Star的堆操作是O(log N)。如果启发函数不能显著减少探索节点，这反而会成为负担。
  3. 已访问状态处理：A-Star中，一个节点可能会被多次加入open_set（当找到更短的g_score时）。我们需要通过比较g_score来更新，而不是简单用一个visited集合阻止第二次访问。这增加了逻辑复杂性。

个人经验：在LeetCode 127这道题上，双向BFS通常是实践中最快、最稳定的选择。A-Star的理论很优美，但实现稍复杂，且由于本题的图结构相对简单，启发函数的收益有时不足以抵消优先级队列的开销。在面试中，如果时间允许，可以先实现双向BFS，然后提到A-Star作为一种可能的优化思路，并讨论其启发函数的设计，这能很好地展示你的知识广度。

6. 总结对比与实战选择

至此，我们已经分析了解决“单词接龙”问题的三种主要思路：单向BFS、双向BFS和A-Star搜索。我们来做一个总结性的对比，并给出实战建议。

特性	单向BFS	双向BFS	A-Star
核心思想	从起点出发，逐层盲目搜索	从起点和终点同时出发，双向“夹击”	利用启发函数，优先搜索“希望更大”的节点
时间复杂度	O(N * L^2)	O(N * L^2)	最坏 O(N log N)
空间复杂度	O(N * L)	O(N * L)	O(N * L)
最优解保证	是	是	是（需启发函数可采纳）
代码复杂度	简单	中等	中等偏上
平均性能	稳定，但较慢	通常最快	依赖于启发函数，不稳定
适用场景	通用，图规模小	起点终点明确，图规模大或路径长	启发函数有效，且图规模大

给不同场景下的选择建议：

1. 面试场景：

   • 首选双向BFS。它能显著体现你对基础算法的优化能力。实现时，务必讲清楚“为什么双向搜索能更快”（减少搜索空间），并注意处理好队列交换和相遇判断的逻辑。
   • 备选单向BFS。如果时间紧张，或者担心双向BFS写错，那么一个正确、清晰、使用了虚拟节点法的单向BFS实现绝对可以让你通过面试。一定要解释清楚虚拟节点法的原理。

2. 竞赛场景：

   • 通常双向BFS是最优解。在时间限制严格的在线判题系统中，双向BFS在大多数用例下表现最好。
   • 可以尝试A-Star，但需要确保启发函数计算非常快（本题的汉明距离计算是O(L)，可以接受）。有时为了极致优化，会结合双向BFS和A-Star的思想。

3. 工程实践：

   • 如果这是一个需要频繁调用的服务，并且单词列表固定，可以考虑预处理。将构建好的图（邻接表或模式字典）缓存起来，后续的每次查询就只是在这个固定图上进行BFS，速度会快很多。
   • 根据数据特点选择算法。如果单词平均长度很长，那么虚拟节点法的优势更大（因为两两比较法代价更高）。如果单词列表是动态变化的，则需要考虑图的重建成本。

最后几个踩坑点提醒：

• 终点不在列表中：这是最常见的边界条件，必须在开始时检查，否则会死循环或返回错误结果。
• 起点等于终点：题目要求返回1（序列包含起点本身）。
• 已访问集合的标记时机：务必在节点入队时标记，而非出队时。
• 双向BFS的步数计算：相遇时，总步数是两端步数之和，不需要再加1。理解清楚这一点对正确编码至关重要。
• 虚拟节点法的通配符：使用’*‘或其他不在字母表中的字符作为通配符，避免与真实字母混淆。

这道“单词接龙”题之所以经典，是因为它将一个生动的游戏场景，完美地抽象成了一个图论最短路径问题，并串联起了BFS、双向BFS、A-Star等多个重要的算法思想。掌握它，不仅是为了通过一道面试题，更是为了深入理解“建模”和“搜索优化”这两项解决复杂问题的核心能力。下次遇到类似的转换、状态搜索问题，不妨先想想：能不能把它变成一张图？