在 Python 中找到将一个单词更改为另一个单词所需的步骤数量的程序

在 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

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程