Pythonで同じ文字列を2回連結したものとして文字列を作成するために必要な操作の数をカウントするプログラム

小文字の文字列sがあるとします。ここで、s内の任意の文字を削除、挿入、または更新できる操作について考えてみます。任意の文字列tに対してs=（t連結t）にするために必要な操作の最小数をカウントする必要があります。

したがって、入力がs ="pqrxqsr"の場合、出力は2になります。これは、"x"を"p"で更新し、 "s"を削除できるため、sは "pqrpqr"、これはs =tはtを連結します。t="pqr"の場合。

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

• 関数edit_distance（）を定義します。これにはs1、s2が必要です
• m：=s1のサイズ
• n：=s2のサイズ
• cur：=0からnまでの新しいリスト
• 0からm-1の範囲のiの場合、do
  • prev：=cur
  • cur：=（i + 1）とn個の0のリスト
  • 0からn-1の範囲のjの場合、do
    • cur [j + 1]：=prev [j]（s1[i]とs2[j]が同じ場合）それ以外の場合（cur [j]、prev [j]、prev [j + 1]の最小値）+ 1
• return cur [n]
• メインの方法から、次の手順を実行します-
• res：=sのサイズ
• 範囲0からs-1のサイズのiの場合、do
  • res：=最小のedit_distance（インデックス0からi-1までのsのサブストリング、インデックスiからendまでのsのサブストリング）とres
• return res

例

理解を深めるために、次の実装を見てみましょう-

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"

出力

None