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

मान लीजिए कि हमारे पास दो स्ट्रिंग्स 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 से मी की सीमा में, करो
- j के लिए 1 से n की सीमा में, करें
  - अगर 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])
वापसी तालिका [एम, एन]
मुख्य विधि से निम्न कार्य करें
एम:=ए का आकार, एन:=बी का आकार
सी :=0
मेरे लिए 0 से मी की सीमा में, करें
- c :=c + ASCII of a[i] - 48
मेरे लिए 0 से n की सीमा में, करें
- c :=c + ASCII का 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"