寻找最小删除以在 Python 中生成字符串的程序

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

因此，如果输入像 s = "pipe" t = "ripe"，那么输出将是 2，因为我们可以从 s 中删除 "p" 并从 t 中删除 "r" 以使这些字符串相同 "ipe"

示例

让我们看看以下实现以获得更好的理解 -

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