โปรแกรมค้นหาจำนวนขั้นตอนที่จำเป็นในการเปลี่ยนคำหนึ่งเป็นอีกคำใน Python

สมมติว่าเรามีรายการคำที่เรียกว่าพจนานุกรม และเรามีอีกสองสตริงเริ่มต้นและสิ้นสุด เราต้องการเข้าถึงตั้งแต่ต้นจนจบโดยเปลี่ยนอักขระทีละตัวและแต่ละคำที่ได้ควรอยู่ในพจนานุกรมด้วย คำจะคำนึงถึงขนาดตัวพิมพ์ ดังนั้นเราจึงต้องหาจำนวนขั้นตอนขั้นต่ำที่จะต้องทำในตอนท้าย หากไม่สามารถทำได้ ให้คืนค่า -1

ดังนั้นหากอินพุตเป็นเหมือนพจนานุกรม =["may", "ray", "rat"] start ="rat" end ="may" ผลลัพธ์จะเป็น 3 เนื่องจากเราสามารถเลือกเส้นทางนี้ได้:["rat , "เรย์", "อาจ"].

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

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