在 Python 中找到将一个单词更改为另一个单词所需的步骤数量的程序
假设我们有一个称为字典的单词列表,还有另外两个字符串start和end。 我们要通过每次更改一个字符来从start到达end,并且每个更改的结果单词也应该包含在字典中。单词是区分大小写的。 因此,我们必须找到到达end所需的最小步骤数。 如果不可能,则返回-1。
因此,如果输入类似于dictionary = [“may”, “ray”, “rat”] start = “rat” end = “may”,则输出将为3,因为我们可以选择此路径:[“rat”, “ray”, “may”]。
为了解决这个问题,我们将遵循以下步骤:
dictionary:=一个新集合,其中包含所有唯一存在的元素
q:=双端队列,其中包含一个对(start,1)
while q不为空,执行以下操作
(word,distance):= q的左侧元素,并删除左侧元素
如果单词与end相同,则
返回距离
for i in range 0到单词大小-1,执行以下操作
对于“abcdefghijklmnopqrstuvwxyz”中的每个字符c,都执行以下操作
next_word:=单词从索引0到i-1拼接c拼接单词从索引(i + 1)到末尾
如果next_word在字典中,则
删除字典中的next_word
在队列的末尾插入(next_word,distance + 1)
返回-1
更多Python相关文章,请阅读:Python 教程
示例(Python)
让我们看一下以下实现以更好地理解-
from collections import deque
class Solution:
def solve(self, dictionary, start, end):
dictionary = set(dictionary)
q = deque([(start, 1)])
while q:
word, distance = q.popleft()
if word == end:
return distance
for i in range(len(word)):
for c in "abcdefghijklmnopqrstuvwxyz":
next_word = word[:i] + c + word[i + 1 :]
if next_word in dictionary:
dictionary.remove(next_word)
q.append((next_word, distance + 1))
return -1
ob = Solution()
dictionary = ["may", "ray", "rat"]
start = "rat"
end = "may"
print(ob.solve(dictionary, start, end))
输入
[“may”,“ray”,“rat”],“rat”,“may”
输出
3