Pythonで文字列を回文にするために必要な最小挿入文字数を求めるプログラム

問題の概要

文字列 s が与えられたとき、その文字列を回文（前から読んでも後ろから読んでも同じになる文字列）にするために、最低何文字を挿入する必要があるかを求める問題です。

例えば、s = "mad" の場合、出力は 2 になります。「am」を挿入して「madam」にすれば回文になるためです。

解決のアプローチ

この問題は、区間ごとに状態を管理する再帰的な動的計画法（DP）で効率よく解けます。以下の手順で考えます。

• dp(i, j) という関数を定義します。これは、部分文字列 s[i..j] を回文にするために必要な最小挿入文字数を返します。

• i >= j の場合（部分文字列が空、または1文字しかない場合）、挿入は不要なので 0 を返します。

• s[i] と s[j] が一致する場合、両端はすでに対応しているため dp(i + 1, j - 1) を返します。

• 一致しない場合は、左端に文字を追加するケースと右端に文字を追加するケースのうち小さい方に1を加え、min(dp(i + 1, j), dp(i, j - 1)) + 1 を返します。

• メイン処理では、dp(0, len(s) - 1) を呼び出して結果を取得します。

実装例

以下のコードでは、functools.lru_cache を使ってメモ化を行い、同じ状態の再計算を防いでいます。これにより計算量が O(n²) に抑えられます。

from functools import lru_cache

class Solution:
    def solve(self, s):
        @lru_cache(maxsize=None)
        def dp(i, j):
            if i >= j:
                return 0
            if s[i] == s[j]:
                return dp(i + 1, j - 1)
            else:
                return min(dp(i + 1, j), dp(i, j - 1)) + 1
        return dp(0, len(s) - 1)

ob = Solution()
s = "mad"
print(ob.solve(s))

入力

s = "mad"

出力

2

計算量について

メモ化を使用した場合、状態の組み合わせは O(n²)、各状態の計算は定数時間なので、全体の時間計算量・空間計算量はともに O(n²) となります。メモ化なしの素朴な再帰では最悪 O(2ⁿ) になるため、実用上はキャッシュの利用が重要です。