পাইথনে স্ট্রিং স্ট্রিং তৈরি করতে ন্যূনতম মুছে ফেলার জন্য প্রোগ্রাম

ধরুন আমাদের দুটি ছোট হাতের স্ট্রিং s এবং t আছে, এখন একটি অপারেশন বিবেচনা করুন যেখানে আমরা এই দুটি স্ট্রিংয়ের যেকোনো একটি অক্ষর মুছে ফেলতে পারি। আমাদের s এবং t সমান করার জন্য প্রয়োজনীয় ন্যূনতম সংখ্যক অপারেশন খুঁজে বের করতে হবে।

সুতরাং, যদি ইনপুটটি s ="pipe" t ="ripe" এর মত হয়, তাহলে আউটপুট হবে 2, কারণ আমরা এই স্ট্রিংগুলিকে একই "ipe" করতে s থেকে "p" এবং t থেকে "r" মুছে ফেলতে পারি। পি>

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

m :=s এর আকার
n :=t এর আকার
একটি ফাংশন dp() সংজ্ঞায়িত করুন। এর জন্য i, j
যদি আমি m এর মত হয়, তাহলে
- রিটার্ন n - j
অন্যথায় যখন j n এর মত হয়, তখন
- রিটার্ন m - i
অন্যথায়,
- যদি s[i] t[j] এর মত হয়, তাহলে
  - রিটার্ন dp(i + 1, j + 1)
- অন্যথায়,
  - রিটার্ন 1 + (সর্বনিম্ন dp(i + 1, j) এবং dp(i, j + 1))
প্রধান পদ্ধতি থেকে, dp(0, 0) ফেরত দিন

উদাহরণ

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

def solve(s, t):
   m = len(s)
   n = len(t)

   def dp(i, j):
      if i == m:
         return n - j
      elif j == n:
         return m - i
      else:
         if s[i] == t[j]:
            return dp(i + 1, j + 1)
         else:
            return 1 + min(dp(i + 1, j), dp(i, j + 1))
   return dp(0, 0)

s = "pipe"
t = "ripe"
print(solve(s, t))

ইনপুট

"pipe", "ripe"