পাইথনে এক শব্দ থেকে অন্য শব্দে রূপান্তরের জন্য ন্যূনতম ধাপ গণনা করার প্রোগ্রাম

একটি ডিকশনারি (ওয়ার্ড লিস্ট) এবং দুটি শব্দ start, end দেওয়া আছে। প্রতিটি ধাপে এক ক্যারেক্টার বদলে নये শব্দটি ডিকশনারিতে থাকতে হবে। start থেকে end-এ যেতে ন্যূনতম কত ধাপ লাগবে সেটি বের করতে হবে। সম্ভব না হলে -১ রিটার্ন করুন।

উদাহরণস্বরূপ, dictionary=["may","ray","rat"], start="rat", end="may" হলে আউটপুট ৩ (পথ: rat → ray → may)।

সমাধানের পদ্ধতি (BFS)

dictionary কে সেট-এ কনভার্ট করুন।
queue = deque([(start, 1)])।
কিউ খালি না হওয়া পর্যন্ত:
- (word, dist) = popleft()।
- যদি word == end: dist রিটার্ন করুন।
- প্রতিটি পজিশন i এবং প্রতিটি ক্যারেক্টার c (a-z) এর জন্য:
  - next_word = word[:i] + c + word[i+1:]।
  - যদি next_word in dictionary: ডিকশনারি থেকে রিমুভ করুন (ভিজিটেড मार্ক), কিউ-এ (next_word, dist+1) পুশ করুন।
-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"