পাইথনে দুটি স্ট্রিং থেকে ডিজিট মুছে কমপক্ষে যোগফল বের করার প্রোগ্রাম

ধরুন s এবং t দুটি ডিজিটের স্ট্রিং। আমাদের ডিজিট গুলো মুছে ফেলতে হবে এমনভাবে যাতে: ১) দুটি স্ট্রিং একই হয়, ২) মুছে ফেলা ডিজিট গুলোর যোগফল ন্যূনতম হয়। ন্যূনতম যোগফল রিটার্ন করুন।

উদাহরণস্বরূপ, s = "41272", t = "172" হলে আউটপুট হবে 6, কারণ প্রথম স্ট্রিং থেকে "4" ও "2" মুছে দিলে "172" পাওয়া যায়।

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

lcs() ফাংশন ডিফাইন করুন যা a, b, m, n নেয়
table := (n+1) x (m+1) আকারের ২D ম্যাট্রিক্স, ০ দিয়ে ভরা
i = 1 থেকে m পর্যন্ত লুপ:
- j = 1 থেকে n পর্যন্ত লুপ:
  - যদি a[i-1] == b[j-1] হয়:
    - table[i][j] := table[i-1][j-1] + 2*(ASCII(a[i-1]) - 48)
  - অন্যথায়:
    - table[i][j] := max(table[i-1][j], table[i][j-1])
table[m][n] রিটার্ন করুন
মূল মেথড থেকে:
- m := a-এর আকার, n := b-এর আকার
- c := 0
- i = 0 থেকে m-1: c += ord(a[i]) - 48
- i = 0 থেকে n-1: c += ord(b[i]) - 48
- result := c - lcs(a, b, m, n)
- result রিটার্ন করুন

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

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"