单词阶梯

2025年2月6日 | 阅读12分钟

引言

单词接龙的定义是达到目标单词的最短链的长度。

挑战在于找到一系列最短的变形，通过一组允许的变形将一个给定单词变成另一个。每次变形只改变一个字母，并且执行的单词必须在一个手写的单词列表中，称为单词列表。需要注意的重要规则是，变形序列中的每个单词都必须在单词列表中（开始单词除外），目标单词必须通过这些变形达到，并且每个转换的单词与序列中的前一个单词只能有一个字母不同。关键在于找到实现这一目标所需的最小变形次数。但是，如果不可能将开始单词转换为目标单词，则结果应返回0。

给定一个词汇表和两个长度相同的单词“start”和“target”，找到从“start”到“target”的最短链的长度（如果存在），类似于现实情况是序列中的每个短语都是一个真正的单词——即它出现在这个词汇表中——并且它旁边的单词在他们的一个字符上是相同的。可以假定“target”单词存在于词汇表中，并且所有字典单词的长度都相同。

直观理解

该问题结果背后的直觉是，将变形视为图的遍历方式，其中每个节点是一个单词，每条边代表一次有效的单字母变形。由于我们想要找到最短的变形序列，广度优先搜索（BFS）是一种自然的选择。BFS逐个位置地探索邻居节点，这保证了当我们第一次访问目标节点（即结束单词）时，我们已经走了最少的路径。

该结果采用了双向 BFS 以获得更好的效果。我们同时从 begin_word 和 end_word 开始探索，几乎在中间相遇，而不是在 begin_word 和 end_word 之间扫描。这可以显著减少搜索空间或空间复杂度，从而降低时间复杂度，尤其是在单词列表很大的情况下。

当前单词的每个字母依次被替换为“a”到“z”中的每个字母，然后检查新单词是否是有效的变形（即，是否存在于单词列表中）。如果有效且以前未被遇到过（不在已访问列表中），则将其添加到搜索的下一个位置。

该算法维护两个范围和两个列表，每个列表代表从原始或开始到结束的 BFS 搜索的当前位置。当两个列表都建立了一个新单词时，就意味着我们在开始和结束之间建立了一个连接，从而获得了最小的变形次数。

但是，如果我们用完所有可能性而两个搜索没有相遇，则不存在有效的变形序列，并且函数返回0。如果两个搜索相遇，我们通过将两边的路径数相加来计算总变形次数。

解决方案方法

该结果应用了双向广度优先搜索（BFS）算法。执行过程中涉及的关键因素和过程包括：

数据结构：为了有效地进行访问和搜索操作，该算法使用了集合（set）和单词列表（list）。具体来说，使用一个名为 words 的集合来存储单词列表，以实现常数时间内的单词确认。两个列表（m1 和 m2）用于跟踪从 begin_word 和 end_word 到搜索过程中遇到的任何给定单词的路径数。两个队列（q1 和 q2）维护从不同起始点开始的 BFS 搜索的每个位置的当前单词序列。

初始化：该算法使用 begin_word 和 end_word 初始化列表，并将它们的值设置为 0，因为最初只走了 0 步。同样，队列也用 begin_word 和 end_word 初始化。

BFS 函数

该结果的核心在于 extend 函数，该函数对开始队列（q1）或结束队列（q2）执行一次 BFS 搜索。它遍历当前队列中的所有单词，并对每个单词：

它尝试将每个字母位置替换为“a”到“z”中的每个字母。

如果新单词存在于 words 中，并且在其自己方向的列表或单词列表中尚未出现过（以避免循环），则继续进行。

它检查新单词是否存在于相反方向的列表中（m2），这意味着已建立连接，并返回总路径数。

如果尚未建立连接，则将新单词添加到列表中，步数增加，并添加到队列中以供进一步搜索。

双向 BFS 执行

该算法交替扩展 q1 和 q2，始终选择较小的队列先扩展。这样做是为了在任何给定时间保持搜索空间尽可能小。

终止和结果计算：搜索以双向方式继续，直到两个搜索之间建立连接，这表示成功的变形序列。将返回总路径数。

如果两个队列都变空，则意味着已探索了所有可能的路径而未能找到 begin_word 和 end_word 之间的连接。在这种情况下，函数返回 0。

通过这种方法，我们可以有效地找到由允许或可能的单词变形产生的搜索空间中的最短路径（最小变形次数），或者确定这样的路径不存在。

示例演练

假设我们有以下脚本

Begin_Word“hit”

End_Word“cog”

Word_List（“hot”，“fleck”，“canine”，“lot”，“log”，“cog”）

我们要将“hit”转换为“cog”。每次变形改变一个字母，因此我们只从单词列表中取有效的变形。那么结果是如何工作的呢？

初始化：words 是一个包含单词{"hot", "fleck", "canine", "lot", "log", "cog"}的集合。

列表 m1 和 m2 被创建，键分别为 begin_word 和 end_word。m1 = {"hit": 1}, m2 = {"cog": 1}

队列 q1 和 q2 初始化为 begin_word 和 end_word。q1 = ("hit"), q2 = ("cog")

BFS 执行

第一个位置：从开始单词（“hit”）开始搜索
算法考虑“hit”并尝试将每个字母替换为“a”到“z”中的每个字母。
它找到“hot”作为单词集合中的有效单词，并且不在 m1 中。
“hot”被添加到列表中，步数为 2（m1 = {"hit": 1, "hot": 2}），并添加到 q1。从 end_word（“cog”）开始的第一级搜索
对“cog”执行类似的操作。
它找到“canine”和“log”作为有效的变形。
它们被添加到 m2 和 q2 中。m2 = {"cog": 1, "canine": 2, "log": 2}。
交替位置：现在，“hot”是 Q1 中的下一个项目。
它找到“fleck”和“lot”作为有效的变形。
它们被添加到 m1 和 q1 中以供下次搜索。
m1 = {"hit": 1, "hot": 2, "fleck": 3, "lot": 3}。
交替位置：从“canine”和“log”开始搜索。
对于“canine”，一个可能的变形是“fleck”，它存在于 m1 中。
这表明我们通过“fleck”建立了一个连接。

通过此连接，两端当前的计数是 m1（“fleck”）= 3 和 m2（“canine”）= 2，因此总和是 3 + 2 - 1 = 4。（我们减去 1 是因为“fleck”是从两边计算的）。

终止和结果

由于我们通过“fleck”建立了连接，我们可以停止搜索。最小变形序列是：“hit”→“hot”→“fleck”→“canine”→“cog”。（或者，一个可能的路径是：“hit”→“hot”→“lot”→“log”→“cog”）

将“hit”转换为“cog”所需的最小变形次数是 4。

此示例说明了双向 BFS 如何在两端同时进行，为单词变形问题找到具有最少路径数的最佳路径。

方法

解决此问题的思路是使用 BFS。要通过 BFS 找到最短路径，请从原始或开始单词开始，并将其推入队列。一旦目标首次出现，也返回 BFS 遍历的那个位置。在 BFS 的每一步中，都可以获得以多种方式形成的所有单词，因此，每当目标单词首次出现时，它就是最短单词链的长度。

从给定的原始或开始单词或 start 单词开始。

将单词推入队列。

运行一个循环直到队列为空。

遍历所有与其相邻（相差一个字符）的单词，并将单词推入队列（用于 BFS）。

持续进行，直到找到目标单词或我们已经覆盖了所有单词。

时间复杂度

O (N ² * M)，其中 N 是词汇表中的条目数，M 是字符串的长度。

辅助空间：O (M * N)

实现代码

# Python3 program to find the length of the
# shortest chain transformation from source
# to target
from collections import deque
# Returns length of shortest chain
# to reach 'target' from 'start'
# Using the minimum number of adjacent
# moves. D is dictionary
def shortestChainLen(start, target, D):
 if start == target:
     return 0
 # If the target is not
 # present in the dictionary
 if target is not in D:
  return 0
 # To store the current chain length
 # and the length of the words
 level, wordlength = 0, len(start)
 # Push the starting word into the queue
 Q = deque()
 Q.append(start)
 # While the queue is non-empty
 while (len(Q) > 0):
  # Increment the chain length
  level += 1
  # Current size of the queue
  sizeofQ = len(Q)
  # Since the queue is being updated while
  # it is being traversed so that only the
  # elements that were already present
  # in the queue before the start of this
  # loop will be traversed for now
  for i in range(sizeofQ):
   # Remove the first word from the queue
   word = [j for j in Q.popleft()]
   #Q.pop()
   # For every character of the word
   for pos in range(wordlength):
    # Retain the original character
    # at the current position
    orig_char = word[pos]
    # Replace the current character with
    # Every possible lowercase alphabet
    for c in range(ord('a'), ord('z')+1):
     word[pos] = chr(c)
     # If the new word is equal
     # to the target word
     if ("".join(word) == target):
      return level + 1
     # Remove the word from the set
     # if it is found in it
     if ("".join(word) not in D):
      continue
      
     del D["".join(word)]
     # And push the newly generated word
     # which will be a part of the chain
     Q.append("".join(word))
    # Restore the original character
    # at the current position
    word[pos] = orig_char
 return 0
# Driver code
if __name__ == '__main__':
 # Make dictionary
 D = {}
 D["poon"] = 1
 D["plee"] = 1
 D["same"] = 1
 D["poie"] = 1
 D["plie"] = 1
 D["poin"] = 1
 D["plea"] = 1
 start = "toon"
 target = "plea"
 print("The list of words are:\n",D)
 print("The initial word is as follows:\n",start)
 print("The target word is as follows:\n",target)
 print("Length of shortest chain is: ",
 shortestChainLen(start, target, D))

输出

说明

提供的 Python 代码证明了这一点，该代码使用词汇表中的表达式，找出从开始单词到目标单词的最短链变形的长度。

1. 函数描述

shortestChainLen 函数接受三个参数：start（开始单词），target（目标短语），以及 D（一个单词词汇表）。

2. 基本情况

如果开始短语与目标短语完全相同，则函数返回零，因为不需要任何变形。

如果目标单词不在词汇表 D 中，则函数也返回零，因为它无法到达。

3. 初始化

位置和单词长度变量初始化为 0，并单独确定开始短语的长度。

初始化一个双端队列 Q 来在 BFS 遍历期间保存短语。

4. 广度优先搜索 (BFS)

当队列 Q 不为空时，该函数迭代处理队列中的短语。

每次变化，它会增加数量（链长度）1。

5. 单词转换

对于队列中的每个单词，它通过一次更改一个字符来生成所有可能的短语。

如果新短语与目标单词匹配，则返回新阶段 1（考虑到我们是从开始到结束计算变形）。

6. 字典操作

一旦单词被访问，它就会从词汇表 D 中移除，以避免重复考虑。

7. 队列更新

它将新生成的短语附加到队列中以供进一步讨论。

8. 恢复

在探索完一个单词的所有可能性之后，它会在移至下一个单词之前将原始单词恢复到当前函数。

9. 终止

如果没有观察到变形序列，则返回零。

这一系列规则有效地通过使用 BFS 来寻找最短的变形集合，探索所有可能的单词组合，同时保留变形期间的单词。

备选实现

维护中间单词和原始单词的映射。

以下是该方法的一个重要贡献。

然后，在这种方法中，我们找出原始或开始单词的所有中间单词以及给定单词列表中的单词，并维护一个中间单词的列表和一个原始单词的向量（list）。例如，对于单词“poon”，中间单词是“*oon”，“p*on”，“po*n”和“ppo*”。此外，我们执行 BFS 遍历，从原始或开始单词开始，并将原始或开始单词和距离的对（pair(word, distance)）推入队列，直到我们到达目标单词。此外，距离就是我们的答案。

实现代码

#python code for the implementation of the above approach.
from typing import List, Tuple, Set, Dict, Any, Union
def shortestlen(source: str, target: str, WordList: Set[str]) -> int:
	if source == target:
		return 0
	# Dictionary of intermediate words and the list of original words is given as follows.
	umap: Dict[str, List[str]] = {}
	# Initialize umap with empty lists
	for i in range(len(source)):
		im_words = source[:i] + "*" + source[i+1:]
		umap[im_words] = []
	# Finding all the intermediate words for the source to target words in words in the given Set
	For words in WordList:
		for i in range(len(word)):
			im_words = word[:i] + "*" + word[i+1:]
			if im_words not in umap:
				umap[im_words] = []
			umap[im_words].append(word)
	# Perform BFS and push (word, distance)
	q = [(source, 1)]
	visited = {source: 1}
	# Traverse until the queue is empty
	while q:
		word, dist = q.pop(0)
		# If the target word is found in the WordList
		if word == target:
			return dist
		# Finding intermediate words for the word in front of the queue
		for i in range(len(word)):
			im_words = word[:i] + '*' + word[i+1:]
			vect = umap[im_words]
			for k in range(len(vect)):
				# If the word is not visited in the WordList
				if vect[k] not in visited:
					visited[vect[k]] = 1
					q.append((vect[k], dist + 1))
	return 0
# Test
# Make dictionary
WordList = {'poon,' 'please,' 'same,' 'poie,' 'plie,' 'point,' 'plea'}
source = "toon"
target = "plea"
print('The source word is:\n',source)
print('The target word is:\n',target)
print('The list of the words are:\n',WordList)
print(f"Length of shortest chain is: {shortestlen(source, target, WordList)}")

输出

上述代码的输出如下：

说明

1. 函数描述

shortestlen 函数接受三个参数：source（开始单词），target（目标短语），以及 WordList（中间单词的固定列表）。

2. 初始化

该函数初始化一个空的词典或 wordlist umap 来存储中间短语及其对应的原始单词。

3. 中间单词映射

对于源单词中的每个函数，该函数通过将该字符替换为通配符'*'来生成中间短语。这些中间单词也保存在 umap 词典中。

4. 将原始单词映射到中间单词

该函数迭代 WordList 中的每个短语。对于每个单词，它以类似的方式生成中间单词，并将与每个中间单词对应的唯一短语保存在 umap 词典中。

5. 广度优先搜索 (BFS)

执行 BFS 以检测从源单词到目标单词的最短变形序列。

6. 队列初始化

BFS 通过用源短语和距离 1 初始化队列（q）来开始执行。

7. 访问集合

使用一个名为 visited 的集合来跟踪已访问的短语，以避免重复访问相同的短语。

8. BFS 循环

BFS 继续执行，直到队列变空。在每次迭代中，一个单词从队列的前面出队。

9. 目标检查

如果出队短语等于目标短语，则函数返回距离。

10. 生成中间单词

对于出队的单词，生成中间短语，并从 umap 词典中检索相应的原始单词。

11. 邻居探索

对于每个检索到的唯一单词，如果它之前未被访问过，则将其标记为已访问，并更新其与源单词的距离。该短语也连同距离增加 1 一起被添加到队列中。

12. 返回

如果未发现变形集合，则函数返回 0。

13. 测试

代码包含一个测试用例，其中将一个单词短语列表与源短语和目标短语一起传递。计算并打印最短变形序列的长度。

总的来说，该代码有效地利用 BFS 来寻找从源短语到目标短语的最短变形序列，并使用中间单词来发现可能的变体。

下一个主题Cuckoo-hashing-worst-case-o-1-lookup

← 上一个下一个 →

单词阶梯

引言

直观理解

解决方案方法

BFS 函数

双向 BFS 执行

示例演练

BFS 执行

终止和结果

方法

实现代码

说明

备选实现

实现代码

说明

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

数据结构教程

DS 数组

DS 链表

DS 栈

DS 队列

DS 树

DS 图

DS 搜索

DS 排序

哈希与堆

差异

二叉树

二叉搜索树

AVL 树

单向链表

双向链表

循环链表

循环双向链表

DS 选择题

其他

单词阶梯

引言

直观理解

解决方案方法

BFS 函数

双向 BFS 执行

示例演练

BFS 执行

终止和结果

方法

实现代码

说明

备选实现

实现代码

说明

相关帖子

生成所有子数组

N 元树的所有元素之和

哈希导论

勾股定理三元组哈希问题

未排序数组的平均值和中位数程序

程序以揭示扫雷中的位置

打印 1 到 N，不使用循环

数据结构中的老鼠进迷宫问题

以垂直顺序打印二叉树

Boruvka 算法求最小生成树

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器