【Python】文字列を「同じ文字列の2回連結(t+t)」にするために必要な最小操作回数を求めるプログラム

小文字のみで構成された文字列 s が与えられているとします。ここで使用できるのは、次の3種類の操作です。

• 任意の1文字を削除する
• 任意の位置に1文字を挿入する
• 任意の1文字を別の文字に更新(置き換え)する

これらの操作を組み合わせて、s を「ある文字列 t を2回連結した形(s = t + t)」に変換するとき、必要となる最小の操作回数を求めるのが本記事のテーマです。

たとえば、入力が s = "pqrxqsr" の場合、答えは 2 になります。「x」を「p」に更新し、「s」を削除すれば s = "pqrpqr" となり、t = "pqr" を2回連結した文字列と一致するためです。

解き方のアプローチ

この問題は編集距離(レーベンシュタイン距離)の動的計画法(DP)を応用することで解けます。ポイントは、文字列を前半と後半に分割できるすべての位置について「前半を後半と一致させるまでの編集距離」を計算し、その最小値を答えとする点です。前半を後半に揃えるのに必要な操作を元の文字列に適用すれば、全体が必ず t + t の形になるためです。

edit_distance 関数の手順

• 2つの文字列 s1、s2 を受け取る関数 edit_distance() を定義します
• m := s1 の長さ
• n := s2 の長さ
• cur := 0 から n までの値を持つリストで初期化(空文字列との距離)
• i を 0 から m-1 まで繰り返します:
  • prev := cur
  • cur := [i + 1] と n 個の 0 からなる新しいリスト
  • j を 0 から n-1 まで繰り返します:
    • s1[i] と s2[j] が等しければ cur[j + 1] := prev[j]、そうでなければ cur[j + 1] := min(cur[j], prev[j], prev[j + 1]) + 1
• cur[n](= 2つの文字列間の編集距離)を返します

メイン処理の手順

• res := s の長さ(初期値。すべての文字を書き換えれば必ず条件を満たせるため)
• i を 0 から len(s)-1 まで繰り返します:
  • res := min(edit_distance(s[:i], s[i:]), res)
• res を返します

実装例

理解を深めるために、以下のPythonコードをご覧ください。

def solve(s):
    def edit_distance(s1, s2):
        m, n = len(s1), len(s2)
        cur = list(range(n + 1))
        for i in range(m):
            prev, cur = cur, [i + 1] + [0] * n
            for j in range(n):
                cur[j + 1] = (prev[j]
                              if s1[i] == s2[j]
                              else min(cur[j], prev[j], prev[j + 1]) + 1)
        return cur[n]

    res = len(s)
    for i in range(len(s)):
        res = min(edit_distance(s[:i], s[i:]), res)
    return res

s = "pqrxqsr"
print(solve(s))

入力

"pqrxqsr"

出力

2

計算量について

分割位置は最大で n+1 通りあり、それぞれの編集距離の計算に O(n²) かかるため、全体の計算量は O(n³) 程度になります。とはいえ、文字列長が数百程度であれば十分実用的な速度で動作するアルゴリズムです。