Pythonで2つの文字列を一致させるために削除する数字の合計の最小値を求めるプログラム

問題の概要

数字のみで構成された2つの文字列 s と t が与えられたとします。それぞれの文字列からいくつかの数字を削除し、以下の条件を満たすようにします。

1. 2つの文字列が同一になること
2. 削除した数字の合計が最小になること

そして、その最小化された合計値を返すのが目的です。

例えば、入力が s = "41272"、t = "172" の場合、出力は 6 になります。これは、最初の文字列から「4」と「2」を削除すれば「172」に一致させることができ、削除した数字の合計は 4 + 2 = 6 となるためです。

解決のアプローチ：LCS(最長共通部分列)の応用

この問題は、動的計画法(DP)による最長共通部分列(LCS)のアルゴリズムを応用することで効率的に解けます。

ポイントは、通常のLCSでは共通部分列の「長さ」を最大化しますが、今回は共通して残す数字の「値の合計」を最大化する点です。両方の文字列に共通して存在する数字は削除不要なため、その分だけ削除コストを抑えられます。共通の数字は2つの文字列の両方に残るため、DPテーブルにはその数字の値を2倍して加算します。

全体の流れは以下の通りです。

• 関数 lcs() を定義します。引数は a、b、m(aの長さ)、n(bの長さ)
• (m+1) × (n+1) のサイズの2次元テーブルを作成し、すべて0で初期化します
• i を 1 から m まで繰り返します
  • j を 1 から n まで繰り返します
    • a[i-1] と b[j-1] が同じ文字の場合:table[i][j] = table[i-1][j-1] + 2 * (a[i-1]のASCIIコード - 48)
    • それ以外の場合:table[i][j] = max(table[i-1][j], table[i][j-1])
• table[m][n] を返します

メインの処理では次を行います。

• m := a の長さ、n := b の長さ
• c := 0 として初期化
• a の各桁の値を c に加算
• b の各桁の値も c に加算
• result := c - lcs(a, b, m, n)
• result を返す

つまり「全数字の合計」から「共通して残せる数字の合計(2倍込み)」を引けば、削除が必要な数字の合計の最小値が求まります。

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

まとめ

このアルゴリズムの計算量は O(m × n) であり、文字列の長さに対して効率的に動作します。ord(文字) - 48 という処理は、ASCIIコード上で「0」が48に対応していることを利用し、文字型の数字を整数値に変換する定番のテクニックです。LCSの考え方を重み付きの問題に拡張する良い例なので、動的計画法の学習にもおすすめです。