পাইথনে একটি ভুল বানান ঠিক করতে মোট কতগুলি অক্ষর পরিবর্তন করতে হবে তা খুঁজে বের করার প্রোগ্রাম

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

সুতরাং, যদি ইনপুট হয় শহর =["HWH", "DLI", "BGL"], রাস্তা =[["HWH", "DLI"],["DLI", "BCT"], ["BCT" , "HWH"]], তাহলে আউটপুট হবে 2।

শহরে ভুল বানান শহরের নাম 'BGL'। সঠিক নাম হবে 'BCT'। সুতরাং, শহরগুলির নামও সংশোধন করুন আমাদের 2টি অক্ষর পরিবর্তন করতে হবে।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• একটি ফাংশন diff() সংজ্ঞায়িত করুন। এটি একটি, b
  লাগবে
  • a এবং b-এর মধ্যে অক্ষরের মোট পার্থক্য ফেরত দিন
• আকার :=শহরগুলির আকার
• arr :=একটি নতুন মানচিত্র
• জংশন :=রাস্তার প্রতিটি উৎস শহর থেকে একটি নতুন সেট
• জংশনে প্রতিটি j-এর জন্য, করুন
  • arr[j] :=diff(cities[0], j)
• আমি রেঞ্জ 1 থেকে আকারের জন্য, কর
  • nxt :=একটি নতুন মানচিত্র
  • রাস্তায় প্রতিটি r1, r2 এর জন্য, করুন
    • যদি r1 arr-এ উপস্থিত থাকে, তাহলে
      • খরচ :=arr[r1] + diff(cities[i], r2)
      • যদি nxt-এ r2 উপস্থিত না থাকে বা মূল্য
      • nxt[r2] :=খরচ
• arr :=nxt

উদাহরণ

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

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"]]

আউটপুট

2