在Python中查找使两个字符串相等的最小删除次数的程序

假设我们有两个小写字符串s和t，现在考虑一个操作，我们可以删除任何一个字符串中的任何字符，我们必须找到使s和t相等所需的最小操作数。

因此，如果输入为s =“pipe”t =“ripe”，则输出将为2，因为我们可以从s中删除“p”和从t中删除“r”以使这些字符串相同“ipe”

要解决此问题，我们将按照以下步骤执行 –

m：s的大小
n：t的大小
定义函数dp（）。这将采取i，j
如果i与m相同，那么
- 返回n – j
否则，当j与n相同时，
- 返回m – i
否则，
- 如果s [i]与t [j]相同，则
  - 返回dp（i + 1，j + 1）
- 否则，
  - 返回1 +（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))