Chương trình tìm số bước cần thiết để thay đổi từ này sang từ khác trong Python

Giả sử chúng ta có một danh sách các từ được gọi là từ điển và chúng ta có hai chuỗi khác bắt đầu và kết thúc. Chúng tôi muốn tiếp cận từ đầu đến cuối bằng cách thay đổi từng ký tự một và mỗi từ kết quả cũng phải có trong từ điển. Các từ có phân biệt chữ hoa chữ thường. Vì vậy, chúng tôi phải tìm số bước tối thiểu mà nó sẽ đạt được khi kết thúc. Nếu không thể, hãy trả về -1.

Vì vậy, nếu đầu vào giống như dictionary =["may", "ray", "rat"] start ="rat" end ="may", thì đầu ra sẽ là 3, vì chúng ta có thể chọn đường dẫn này:["rat "," ray "," may "].

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

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

Ví dụ (Python)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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))

Đầu vào

["may", "ray", "rat"], "rat", "may"

Đầu ra

3