程序查找在Python中将一个单词转换为另一个单词所需的步骤数
假设我们有一个称为字典的单词列表，还有另外两个字符串start和end。我们希望通过一次更改一个字符来达到从头到尾的效果，每个产生的单词也应放在字典中。单词区分大小写。因此，我们必须找到最终要达到的最小步骤数。如果不可能，则返回-1。
因此，如果输入是dictionary=[[“may”，“ray”，“rat”]start=“rat”end=“may”，那么输出将是3，因为我们可以选择这条路径:[“rat”，“ray”，“may”]。
为了解决这个问题，我们将遵循以下步骤-
dictionary := a new set with all unique elements present in
q = a double ended queue with a pair (start, 1)
while q is not empty, do
(word, distance) := left element of q, and delete the left element
if word is same as end, then
return distance
for i in range 0 to size of word - 1, do
for each character c in "abcdefghijklmnopqrstuvwxyz", do
next_word := word[from index 0 to i - 1] concatenate c concatenate word[from index (i + 1) to end]
if next_word is in dictionary, then
delete next_word from dictionary
insert (next_word, distance + 1) at the end of q
return -1范例(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