Pythonで文字列文字列を作成するための最小限の削除を見つけるプログラム

2つの小文字の文字列sとtがあるとします。ここで、これら2つの文字列のいずれかで任意の文字を削除できる操作について考えてみます。 sとtを等しくするために必要な操作の最小数を見つける必要があります。

したがって、入力がs ="pipe" t ="ripe"の場合、出力は2になります。これは、sから "p"を削除し、tから "r"を削除して、これらの文字列を同じ"ipe"にすることができるためです。

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

• m：=sのサイズ
• n：=tのサイズ
• 関数dp（）を定義します。これにはi、jが必要です
• iがmと同じ場合、
  • return n --j
• それ以外の場合、jがnと同じである場合、
  • return m-i
• それ以外の場合、
  • s[i]がt[j]と同じ場合、
    • return dp（i + 1、j + 1）
  • それ以外の場合、
    • return 1 +（dp（i + 1、j）およびdp（i、j + 1）の最小値）
• mainメソッドから、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