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

ধরুন আমরা একটি ছোট হাতের স্ট্রিং s আছে. এখন একটি অপারেশন বিবেচনা করুন, যেখানে আমরা s-এর যেকোনো অক্ষর মুছতে, সন্নিবেশ বা আপডেট করতে পারি। যেকোন স্ট্রিং t এর জন্য s =(t concatenate t) করার জন্য আমাদের প্রয়োজনীয় ন্যূনতম সংখ্যক অপারেশন গণনা করতে হবে।

সুতরাং, যদি ইনপুটটি s ="pqrxqsr" এর মতো হয়, তাহলে আউটপুট হবে 2, কারণ, আমরা "p" দিয়ে "x" আপডেট করতে পারি এবং "s" মুছে ফেলতে পারি, তারপর s হল "pqrpqr", এটি s =t concatenate t, t ="pqr" এর জন্য।

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

• একটি ফাংশন সংজ্ঞায়িত করুন edit_distance()। এটি s1, s2
লাগবে৷
• m :=s1 এর আকার
• n :=s2 এর আকার
• cur :=0 থেকে n পর্যন্ত একটি নতুন তালিকা
• আমি 0 থেকে m - 1 রেঞ্জের জন্য, কর
  • পূর্ববর্তী :=cur
  • cur :=(i + 1) সহ একটি তালিকা এবং তারপর 0s এর n সংখ্যা
  0 থেকে n - 1 রেঞ্জে j-এর জন্য
  • করুন
    • cur[j + 1] :=prev[j] যদি s1[i] এবং s2[j] একই হয় অন্যথায় (সর্বনিম্ন cur[j], prev[j], prev[j + 1]) + 1
• রিটার্ন cur[n]
• প্রধান পদ্ধতি থেকে, নিম্নলিখিতগুলি করুন -
• res :=s এর আকার
• আমি 0 থেকে s - 1 এর পরিসরের জন্য, কর
  • res :=ন্যূনতম সম্পাদনা_দূরত্ব (সূচী 0 থেকে i - 1 পর্যন্ত s-এর সাবস্ট্রিং, সূচক i থেকে শেষ পর্যন্ত s-এর সাবস্ট্রিং) এবং res
• রিটার্ন রিটার্ন

উদাহরণ

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

def solve(s):
   def edit_distance(s1, s2):
      m, n = len(s1), len(s2)
      cur = list(range(n + 1))
      for i in range(m):
         prev, cur = cur, [i + 1] + [0] * n
         for j in range(n):
            cur[j + 1] = (prev[j]
            if s1[i] == s2[j] else min(cur[j], prev[j], prev[j + 1]) + 1)
         return cur[n]

   res = len(s)
   for i in range(len(s)):
      res = min(edit_distance(s[:i], s[i:]), res)
   return res

s = "pqrxqsr"
print(solve(s))

ইনপুট

"pqrxqsr"

আউটপুট

None