Pythonで2つの文字列を等しくするための最小削除回数を求めるプログラム

この記事では、2つの小文字からなる文字列 s と t が与えられたとき、それぞれの文字列から任意の文字を1つ削除するという操作を繰り返し、両方の文字列を等しくするために必要な最小の操作回数を求める方法を解説します。

例えば、入力が s = "pipe"、t = "ripe" の場合、出力は 2 になります。これは、s から "p" を、t から "r" をそれぞれ1回ずつ削除すれば、両方の文字列が同じ "ipe" になるためです。

解決のためのアプローチ

この問題は、メモ化再帰（動的計画法）を使って効率的に解くことができます。基本的な考え方は次の通りです。

• m := 文字列 s の長さ
• n := 文字列 t の長さ
• 関数 dp(i, j) を定義します（i は s の位置、j は t の位置を表します）。
• i が m と等しい場合（s をすべて処理済みの場合）：
  • n - j を返す（t の残りの文字をすべて削除する必要がある）
• j が n と等しい場合（t をすべて処理済みの場合）：
  • m - i を返す（s の残りの文字をすべて削除する必要がある）
• それ以外の場合：
  • s[i] が t[j] と一致する場合は、dp(i + 1, j + 1) を返す（削除不要で両方進む）
  • 一致しない場合は、1 + min(dp(i + 1, j), dp(i, j + 1)) を返す（どちらか一方を削除して進む）
• メイン処理では dp(0, 0) を返します。

実装例

理解を深めるために、以下の実装例を見てみましょう。

def solve(s, t):
    m = len(s)
    n = len(t)

    def dp(i, j):
        if i == m:
            return n - j
        elif j == n:
            return m - i
        else:
            if s[i] == t[j]:
                return dp(i + 1, j + 1)
            else:
                return 1 + min(dp(i + 1, j), dp(i, j + 1))
    return dp(0, 0)

s = "pipe"
t = "ripe"
print(solve(s, t))

入力

"pipe", "ripe"

出力

2

最長共通部分列（LCS）との関係

この問題は、最長共通部分列（Longest Common Subsequence: LCS）の考え方と密接に関係しています。まず2つの文字列のLCSの長さ L を求めると、必要な削除回数は次の式で計算できます。

(m − L) + (n − L)

上記の例では、"pipe" と "ripe" のLCSは "ipe"（長さ3）なので、(4 − 3) + (4 − 3) = 2 となり、同じ結果が得られます。

計算量

• 時間計算量： O(m × n) — 各状態 (i, j) を一度だけ計算します。
• 空間計算量： O(m × n) — メモ化に必要なテーブルのサイズに依存します。

素朴な再帰だけでは指数時間かかる可能性がありますが、メモ化やボトムアップのDPテーブルを用いることで、大規模な入力に対しても効率的に処理できるようになります。