পাইথনে মুছে ফেলা ডিজিটের যোগফল ন্যূনতম ডিজিট খুঁজে বের করার প্রোগ্রাম

ধরুন আমাদের কাছে দুটি স্ট্রিং s এবং t ডিজিট আছে, আমাদের স্ট্রিংগুলিতে ডিজিটগুলি সরানোর জন্য একটি উপায় খুঁজে বের করতে হবে যাতে:1. দুটি স্ট্রিং একই 2. মুছে ফেলা সংখ্যাগুলির যোগফল মিনিমাইজ করা হয় অবশেষে মিনিমাইজ করা যোগফল ফেরত দিন।

সুতরাং, যদি ইনপুটটি s ="41272" t ="172" এর মত হয়, তাহলে আউটপুট হবে 6, যেহেতু আমরা "172" পেতে প্রথম স্ট্রিং থেকে "4" এবং "2" সরিয়ে ফেলতে পারি।

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

একটি ফাংশন lcs() সংজ্ঞায়িত করুন। এটি a, b, m, n
লাগবে
টেবিল :=আকারের একটি 2d ম্যাট্রিক্স (n + 1) x (m + 1) এবং 0 দিয়ে পূরণ করুন
1 থেকে m রেঞ্জের জন্য, করুন
- 1 থেকে n রেঞ্জে j এর জন্য, করুন
  - যদি a[i - 1] হয় b[j - 1] এর মত, তাহলে
    - টেবিল[i, j] :=টেবিল[i - 1, j - 1] + 2 *(ASCII of a[i - 1] - 48)
  - অন্যথায়,
    - টেবিল[i, j] =সর্বোচ্চ টেবিল[i - 1, j] এবং টেবিল[i, j - 1])
রিটার্ন টেবিল[m, n]
মূল পদ্ধতি থেকে নিম্নলিখিতগুলি করুন
m :=a এর আকার, n :=b এর আকার
c :=0
0 থেকে m রেঞ্জের জন্য, করুন
- c :=c + ASCII of a[i] - 48
0 থেকে n রেঞ্জের জন্য, করুন
- c :=c + ASCII of b[i] - 48
ফলাফল :=c - lcs(a, b, m, n)
ফেরত ফলাফল

উদাহরণ (পাইথন)

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

class Solution:
   def lcs(self, a, b, m, n):
      table = [[0 for i in range(n + 1)] for j in range(m + 1)]
      for i in range(1, m + 1):
         for j in range(1, n + 1):
            if a[i - 1] == b[j - 1]:
               table[i][j] = table[i - 1][j - 1] + 2 * (ord(a[i - 1]) - 48)
            else:
               table[i][j] = max(table[i - 1][j], table[i][j - 1])
      return table[m][n]
   def solve(self, a, b):
      m = len(a)
      n = len(b)
      c = 0
      for i in range(m):
         c += ord(a[i]) - 48
      for i in range(n):
         c += ord(b[i]) - 48
      result = c - self.lcs(a, b, m, n)
      return result
ob = Solution()
s = "41272"
t = "172"
print(ob.solve(s, t))

ইনপুট

"41272", "172"