在Python中查找删除数字的最小数字和

假设我们有两个数字字符串s和t，我们必须找到一种方法来从这些字符串中删除数字，使得： 1. 两个字符串相同 2. 被删除的数字总和最小最后返回最小化的总和。

因此，如果输入为s =“41272”t =“172”，则输出将为6，因为我们可以从第一个字符串中删除“4”和“2”，以获得“172”。

要解决这个问题，我们将遵循以下步骤：

定义一个函数lcs()。这将采用a，b，m，n
table：一个大小为（n + 1）x（m + 1）的2d矩阵，并填充为0
for i in range 1 to m，do
- for j in range 1 to n，do
  - 如果a [i-1]与b [j-1]相同，则
  - table [i，j]：= table [i – 1，j – 1] + 2 *（a [i-1]的ASCII码-48）
  - 否则，
  - table [i，j] = table [i – 1，j]和table [i，j-1]）的最大值
返回table [m，n]
从主方法执行以下操作
m：a的大小，n：b的大小
c：= 0
for i in range 0 to m，do
- c：= c + a[i]的ASCII码-48
for i in range 0 to n，do
- c：= c + b [i]的ASCII码-48
result：= c-lcs(a，b，m，n)
返回结果

示例（Python）

让我们看一下以下实现，以更好地理解-

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))