পাইথনে একটি শব্দ থেকে অন্য শব্দ পরিবর্তন করার জন্য প্রয়োজনীয় সংখ্যক ধাপ খুঁজে বের করার প্রোগ্রাম

ধরুন আমাদের কাছে অভিধান নামক শব্দের একটি তালিকা আছে এবং আমাদের আরও দুটি স্ট্রিং আছে শুরু এবং শেষ। আমরা এক সময়ে একটি অক্ষর পরিবর্তন করে শুরু থেকে শেষ পর্যন্ত পৌঁছাতে চাই এবং প্রতিটি ফলের শব্দও অভিধানে থাকা উচিত। শব্দগুলি কেস-সংবেদনশীল। তাই শেষ পর্যন্ত পৌঁছাতে আমাদের ন্যূনতম সংখ্যক পদক্ষেপ খুঁজে বের করতে হবে। যদি সম্ভব না হয় তবে -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

উদাহরণ (পাইথন)

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

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