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(i1, 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[i1:] # 当前单词关联到这个模式 pattern_dict[pattern].append(word) # 基于模式字典构建原始单词间的邻接关系 for pattern, words in pattern_dict.items(): # 属于同一模式的所有单词彼此之间都只差一个字母 for i in range(len(words)): for j in range(i1, 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实现需要以下组件队列用于存储待访问的节点并保证“先进先出”的顺序从而实现按层遍历。已访问集合记录已经进入过队列的节点避免重复访问和死循环。距离记录记录每个节点到起点的距离层数。以下是针对本题的BFS实现步骤步骤1预处理与初始化首先将单词列表转换为集合便于 O(1) 时间的查找。同时检查终点是否在列表中如果不在直接返回0。 将起点beginWord加入队列和已访问集合。此时起点距离为1转换序列包含起点本身。步骤2BFS循环主体当队列不为空时循环执行获取当前层的节点数量level_size。这一步是关键它帮助我们区分队列中的节点属于哪一层。循环level_size次每次从队列中取出一个节点current_word。生成current_word的所有可能模式虚拟节点。对于每个模式从pattern_dict中找到所有与之匹配的单词即邻居。遍历这些邻居单词如果邻居是endWord说明找到了终点返回当前距离steps 1因为当前steps是走到current_word的步数再走一步到终点。如果邻居未被访问过则将其标记为已访问并加入队列。当前层所有节点处理完毕后将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[i1:] 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[i1:] 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但在此问题中由于我们只关心最短路径长度且使用层序遍历可以用当前扩展的层来代表距离。算法步骤如下初始化将起点加入queue_begin和visited_begin将终点加入queue_end和visited_end。如果起点和终点相同返回1。交替扩展在每一轮中我们选择当前节点数较少的那一端进行扩展这是一种优化优先扩展规模小的队列有助于更快相遇。这能平衡两边的搜索进度。扩展过程从选中的队列中取出当前层的所有节点。对于每个节点生成其所有邻居。如果某个邻居已经被另一端访问过即在另一端的visited集合中那么我们就找到了连接两端的路径。总路径长度 从起点到当前节点的距离 从终点到该邻居节点的距离 1。否则如果该邻居未被当前端访问过则将其加入当前端的队列和已访问集合。终止条件当某一端的队列为空时说明该方向已无法继续前进而两端仍未相遇则终点不可达。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[i1:] 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[i1:] 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需要注意以下几点状态表示每个状态就是当前单词。代价g(n)从beginWord到当前单词n已经转换的次数。启发函数h(n)h(n) word_diff(n, endWord)即两个单词对应位置字母不同的数量。数据结构open_set一个优先级队列存储待探索的节点按f(n)排序。g_score字典记录从起点到每个节点的最短已知距离g(n)。came_from字典记录每个节点的前驱节点用于最终重构路径本题不需要路径长度但保留此结构有助于理解。算法过程初始化open_set加入起点其f_score h(beginWord)。初始化g_score[beginWord] 0。循环直到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[i1:] 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[i1:] 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)使用汉明距离这是一个可采纳的启发函数因为每次只能改一个字母实际步数不可能比不同字母数少但它的“信息量”有时不够大尤其是在单词长度较短时。陷阱启发函数的质量如果h(n)恒为0A-Star就退化成了Dijkstra算法在无权图中等同于BFS。如果h(n)高估了实际代价A-Star可能找不到最优解。本题的汉明距离是安全的但未必总是高效。优先级队列的开销维护堆结构有额外开销。在本题这种边权为1的图中BFS的普通队列操作是O(1)而A-Star的堆操作是O(log N)。如果启发函数不能显著减少探索节点这反而会成为负担。已访问状态处理A-Star中一个节点可能会被多次加入open_set当找到更短的g_score时。我们需要通过比较g_score来更新而不是简单用一个visited集合阻止第二次访问。这增加了逻辑复杂性。个人经验在LeetCode 127这道题上双向BFS通常是实践中最快、最稳定的选择。A-Star的理论很优美但实现稍复杂且由于本题的图结构相对简单启发函数的收益有时不足以抵消优先级队列的开销。在面试中如果时间允许可以先实现双向BFS然后提到A-Star作为一种可能的优化思路并讨论其启发函数的设计这能很好地展示你的知识广度。6. 总结对比与实战选择至此我们已经分析了解决“单词接龙”问题的三种主要思路单向BFS、双向BFS和A-Star搜索。我们来做一个总结性的对比并给出实战建议。特性单向BFS双向BFSA-Star核心思想从起点出发逐层盲目搜索从起点和终点同时出发双向“夹击”利用启发函数优先搜索“希望更大”的节点时间复杂度O(N * L^2)O(N * L^2)最坏 O(N log N)空间复杂度O(N * L)O(N * L)O(N * L)最优解保证是是是需启发函数可采纳代码复杂度简单中等中等偏上平均性能稳定但较慢通常最快依赖于启发函数不稳定适用场景通用图规模小起点终点明确图规模大或路径长启发函数有效且图规模大给不同场景下的选择建议面试场景首选双向BFS。它能显著体现你对基础算法的优化能力。实现时务必讲清楚“为什么双向搜索能更快”减少搜索空间并注意处理好队列交换和相遇判断的逻辑。备选单向BFS。如果时间紧张或者担心双向BFS写错那么一个正确、清晰、使用了虚拟节点法的单向BFS实现绝对可以让你通过面试。一定要解释清楚虚拟节点法的原理。竞赛场景通常双向BFS是最优解。在时间限制严格的在线判题系统中双向BFS在大多数用例下表现最好。可以尝试A-Star但需要确保启发函数计算非常快本题的汉明距离计算是O(L)可以接受。有时为了极致优化会结合双向BFS和A-Star的思想。工程实践如果这是一个需要频繁调用的服务并且单词列表固定可以考虑预处理。将构建好的图邻接表或模式字典缓存起来后续的每次查询就只是在这个固定图上进行BFS速度会快很多。根据数据特点选择算法。如果单词平均长度很长那么虚拟节点法的优势更大因为两两比较法代价更高。如果单词列表是动态变化的则需要考虑图的重建成本。最后几个踩坑点提醒终点不在列表中这是最常见的边界条件必须在开始时检查否则会死循环或返回错误结果。起点等于终点题目要求返回1序列包含起点本身。已访问集合的标记时机务必在节点入队时标记而非出队时。双向BFS的步数计算相遇时总步数是两端步数之和不需要再加1。理解清楚这一点对正确编码至关重要。虚拟节点法的通配符使用’*‘或其他不在字母表中的字符作为通配符避免与真实字母混淆。这道“单词接龙”题之所以经典是因为它将一个生动的游戏场景完美地抽象成了一个图论最短路径问题并串联起了BFS、双向BFS、A-Star等多个重要的算法思想。掌握它不仅是为了通过一道面试题更是为了深入理解“建模”和“搜索优化”这两项解决复杂问题的核心能力。下次遇到类似的转换、状态搜索问题不妨先想想能不能把它变成一张图 从单词接龙到图论：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(i1, 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[i1:] # 当前单词关联到这个模式 pattern_dict[pattern].append(word) # 基于模式字典构建原始单词间的邻接关系 for pattern, words in pattern_dict.items(): # 属于同一模式的所有单词彼此之间都只差一个字母 for i in range(len(words)): for j in range(i1, 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实现需要以下组件队列用于存储待访问的节点并保证“先进先出”的顺序从而实现按层遍历。已访问集合记录已经进入过队列的节点避免重复访问和死循环。距离记录记录每个节点到起点的距离层数。以下是针对本题的BFS实现步骤步骤1预处理与初始化首先将单词列表转换为集合便于 O(1) 时间的查找。同时检查终点是否在列表中如果不在直接返回0。 将起点beginWord加入队列和已访问集合。此时起点距离为1转换序列包含起点本身。步骤2BFS循环主体当队列不为空时循环执行获取当前层的节点数量level_size。这一步是关键它帮助我们区分队列中的节点属于哪一层。循环level_size次每次从队列中取出一个节点current_word。生成current_word的所有可能模式虚拟节点。对于每个模式从pattern_dict中找到所有与之匹配的单词即邻居。遍历这些邻居单词如果邻居是endWord说明找到了终点返回当前距离steps 1因为当前steps是走到current_word的步数再走一步到终点。如果邻居未被访问过则将其标记为已访问并加入队列。当前层所有节点处理完毕后将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[i1:] 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[i1:] 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但在此问题中由于我们只关心最短路径长度且使用层序遍历可以用当前扩展的层来代表距离。算法步骤如下初始化将起点加入queue_begin和visited_begin将终点加入queue_end和visited_end。如果起点和终点相同返回1。交替扩展在每一轮中我们选择当前节点数较少的那一端进行扩展这是一种优化优先扩展规模小的队列有助于更快相遇。这能平衡两边的搜索进度。扩展过程从选中的队列中取出当前层的所有节点。对于每个节点生成其所有邻居。如果某个邻居已经被另一端访问过即在另一端的visited集合中那么我们就找到了连接两端的路径。总路径长度 从起点到当前节点的距离 从终点到该邻居节点的距离 1。否则如果该邻居未被当前端访问过则将其加入当前端的队列和已访问集合。终止条件当某一端的队列为空时说明该方向已无法继续前进而两端仍未相遇则终点不可达。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[i1:] 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[i1:] 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需要注意以下几点状态表示每个状态就是当前单词。代价g(n)从beginWord到当前单词n已经转换的次数。启发函数h(n)h(n) word_diff(n, endWord)即两个单词对应位置字母不同的数量。数据结构open_set一个优先级队列存储待探索的节点按f(n)排序。g_score字典记录从起点到每个节点的最短已知距离g(n)。came_from字典记录每个节点的前驱节点用于最终重构路径本题不需要路径长度但保留此结构有助于理解。算法过程初始化open_set加入起点其f_score h(beginWord)。初始化g_score[beginWord] 0。循环直到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[i1:] 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[i1:] 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)使用汉明距离这是一个可采纳的启发函数因为每次只能改一个字母实际步数不可能比不同字母数少但它的“信息量”有时不够大尤其是在单词长度较短时。陷阱启发函数的质量如果h(n)恒为0A-Star就退化成了Dijkstra算法在无权图中等同于BFS。如果h(n)高估了实际代价A-Star可能找不到最优解。本题的汉明距离是安全的但未必总是高效。优先级队列的开销维护堆结构有额外开销。在本题这种边权为1的图中BFS的普通队列操作是O(1)而A-Star的堆操作是O(log N)。如果启发函数不能显著减少探索节点这反而会成为负担。已访问状态处理A-Star中一个节点可能会被多次加入open_set当找到更短的g_score时。我们需要通过比较g_score来更新而不是简单用一个visited集合阻止第二次访问。这增加了逻辑复杂性。个人经验在LeetCode 127这道题上双向BFS通常是实践中最快、最稳定的选择。A-Star的理论很优美但实现稍复杂且由于本题的图结构相对简单启发函数的收益有时不足以抵消优先级队列的开销。在面试中如果时间允许可以先实现双向BFS然后提到A-Star作为一种可能的优化思路并讨论其启发函数的设计这能很好地展示你的知识广度。6. 总结对比与实战选择至此我们已经分析了解决“单词接龙”问题的三种主要思路单向BFS、双向BFS和A-Star搜索。我们来做一个总结性的对比并给出实战建议。特性单向BFS双向BFSA-Star核心思想从起点出发逐层盲目搜索从起点和终点同时出发双向“夹击”利用启发函数优先搜索“希望更大”的节点时间复杂度O(N * L^2)O(N * L^2)最坏 O(N log N)空间复杂度O(N * L)O(N * L)O(N * L)最优解保证是是是需启发函数可采纳代码复杂度简单中等中等偏上平均性能稳定但较慢通常最快依赖于启发函数不稳定适用场景通用图规模小起点终点明确图规模大或路径长启发函数有效且图规模大给不同场景下的选择建议面试场景首选双向BFS。它能显著体现你对基础算法的优化能力。实现时务必讲清楚“为什么双向搜索能更快”减少搜索空间并注意处理好队列交换和相遇判断的逻辑。备选单向BFS。如果时间紧张或者担心双向BFS写错那么一个正确、清晰、使用了虚拟节点法的单向BFS实现绝对可以让你通过面试。一定要解释清楚虚拟节点法的原理。竞赛场景通常双向BFS是最优解。在时间限制严格的在线判题系统中双向BFS在大多数用例下表现最好。可以尝试A-Star但需要确保启发函数计算非常快本题的汉明距离计算是O(L)可以接受。有时为了极致优化会结合双向BFS和A-Star的思想。工程实践如果这是一个需要频繁调用的服务并且单词列表固定可以考虑预处理。将构建好的图邻接表或模式字典缓存起来后续的每次查询就只是在这个固定图上进行BFS速度会快很多。根据数据特点选择算法。如果单词平均长度很长那么虚拟节点法的优势更大因为两两比较法代价更高。如果单词列表是动态变化的则需要考虑图的重建成本。最后几个踩坑点提醒终点不在列表中这是最常见的边界条件必须在开始时检查否则会死循环或返回错误结果。起点等于终点题目要求返回1序列包含起点本身。已访问集合的标记时机务必在节点入队时标记而非出队时。双向BFS的步数计算相遇时总步数是两端步数之和不需要再加1。理解清楚这一点对正确编码至关重要。虚拟节点法的通配符使用’*‘或其他不在字母表中的字符作为通配符避免与真实字母混淆。这道“单词接龙”题之所以经典是因为它将一个生动的游戏场景完美地抽象成了一个图论最短路径问题并串联起了BFS、双向BFS、A-Star等多个重要的算法思想。掌握它不仅是为了通过一道面试题更是为了深入理解“建模”和“搜索优化”这两项解决复杂问题的核心能力。下次遇到类似的转换、状态搜索问题不妨先想想能不能把它变成一张图