পাইথনে ভুল বানান শুদ্ধ করতে কতগুলো ক্যারেক্টার পরিবর্তন দরকার তা বের করার প্রোগ্রাম

একটি সিটি লিস্ট এবং রোড লিস্ট দেওয়া আছে যা সিটি-গুলোক কানেক্ট করে। 'cities' লিস্টে টুর বাস যে ক্রমে সিটি গুলো দেখে তা থাকে। 'roads' লিস্টে রোডগুলো (source, destination) অর্ডারে থাকে অর্থাৎ source থেকে destination-এ একমুখী রোড আছে। সমস্যা হল 'cities' লিস্টে কিছু সিটির নাম ভুল বানান করা থাকতে পারে। এগুলো কমপক্ষে কতগুলো ক্যারেক্টার পরিবর্তন করে শুদ্ধ করা যায় তা বের করতে হবে। পরিবর্তিত ক্যারেক্টার সংখ্যা আউটপুট হিসেবে দিতে হবে।

ইনপুট cities = ["HWH", "DLI", "BGL"], roads = [["HWH", "DLI"], ["DLI", "BCT"], ["BCT", "HWH"]] হলে আউটপুট হবে ২।

cities-এ ভুল বানান করা সিটির নাম 'BGL'। সঠিক নাম হবে 'BCT'। সুতরাং শুদ্ধ করতে ২টি ক্যারেক্টার পরিবর্তন দরকার।

সমাধানের ধাপসমূহ

diff() ফাংশন সংজ্ঞায়িত করুন। এটি a, b গ্রহণ করবে:
- a এবং b-এর মধ্যে ক্যারেক্টার পার্থক্যের মোট সংখ্যা ফেরত দিন
size := cities-এর আকার
arr := একটি নতুন ম্যাপ
junctions := roads-এ থাকা প্রতিটি source সিটি থেকে একটি সেট
junctions-এর প্রতিটি j-এর জন্য:
- arr[j] := diff(cities[0], j)
i = 1 থেকে size পর্যন্ত:
- nxt := একটি নতুন ম্যাপ
- roads-এর প্রতিটি r1, r2-এর জন্য:
  - যদি r1 arr-এ থাকে:
    - cost := arr[r1] + diff(cities[i], r2)
    - যদি r2 nxt-এ না থাকে বা cost < nxt[r2] হয়:
      - nxt[r2] := cost
- arr := nxt
arr-এ থাকা সব মানগুলোর মিনিমাম ফেরত দিন

উদাহরণ

def diff(a, b):
    return sum(x != y for x, y in zip(a, b))

def solve(cities, roads):
    size = len(cities)
    arr = dict()
    junctions = set(r[0] for r in roads)
    for j in junctions:
        arr[j] = diff(cities[0], j)
    for i in range(1, size):
        nxt = dict()
        for r1, r2 in roads:
            if r1 in arr:
                cost = arr[r1] + diff(cities[i], r2)
                if r2 not in nxt or cost < nxt[r2]:
                    nxt[r2] = cost
        arr = nxt
    return min(arr.values())

print(solve(["HWH", "DLI", "BGL"], [["HWH", "DLI"], ["DLI", "BCT"], ["BCT", "HWH"]]))

ইনপুট

["HWH", "DLI", "BGL"], [["HWH", "DLI"], ["DLI", "BCT"], ["BCT", "HWH"]]