पायथन में हटाए गए अंकों के न्यूनतम अंक योग ज्ञात करने का प्रोग्राम

मान लीजिए हमारे पास अंकों की दो स्ट्रिंग्स s और t हैं। हमें स्ट्रिंग्स में अंकों को हटाने का एक तरीका ढूंढना है ताकि: 1. दोनों स्ट्रिंग्स समान हों 2. हटाए गए अंकों का योग न्यूनतम हो। अंत में न्यूनतम योग वापस करें।

उदाहरण के लिए, s = "41272", t = "172" के लिए आउटपुट 6 होगा, क्योंकि हम पहली स्ट्रिंग से "4" और "2" हटाकर "172" प्राप्त कर सकते हैं।

एल्गोरिदम (LCS वेरिएंट)

• lcs(a, b, m, n) फ़ंक्शन परिभाषित करें:
  • table := (n+1) x (m+1) मैट्रिक्स 0 से भरी हुई
  • 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] वापस करें
• मुख्य विधि से:
  • दोनों स्ट्रिंग्स के सभी अंकों का योग c में करें
  • result = c - lcs(a, b, m, n)
  • result वापस करें

उदाहरण

class Solution:
    def lcs(self, a, b, m, n):
        table = [[0]*(n+1) for _ 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, n = len(a), len(b)
        c = sum(ord(ch)-48 for ch in a) + sum(ord(ch)-48 for ch in b)
        return c - self.lcs(a, b, m, n)

ob = Solution()
s = "41272"
t = "172"
print(ob.solve(s, t))

इनपुट

"41272", "172"

आउटपुट

6