Pythonで削除された桁の最小桁の合計を見つけるプログラム

2つの文字列sとtの数字があるとすると、次のように文字列内の数字を削除する方法を見つける必要があります。1.2つの文字列が同じ2.削除される数字の合計が最小化最後に最小化された合計を返します。

したがって、入力がs ="41272" t ="172"の場合、最初の文字列から「4」と「2」を削除して「172」を取得できるため、出力は6になります。

これを解決するには、次の手順に従います-

• 関数lcs（）を定義します。これにはa、b、m、nが必要です

• table：=サイズ（n + 1）x（m + 1）の2d行列で、0を入力します

• 1からmの範囲のiの場合、実行します

  • 1からnの範囲のjについては、次のようにします

    • a[i-1]がb[j-1]と同じ場合、

      • table [i、j]：=table [i-1、j-1] + 2 *（a [i-1]-48のASCII）

    • それ以外の場合

      • table [i、j] =table [i-1、j]およびtable [i、j-1]）の最大値

• リターンテーブル[m、n]

• メインの方法から次のようにします

• m：=aのサイズ、n：=bのサイズ

• c：=0

• 0からmの範囲のiの場合、実行

  • c：=c +a[i]のASCII-48

• 0からnの範囲のiの場合、実行

  • c：=c +b[i]のASCII-48

• 結果：=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))

入力

"41272", "172"

出力

6