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))

输入

"pipe", "ripe"

输出

2

更新于：2021年10月18日

478 次浏览

开启你的职业生涯

完成课程获得认证

开始学习
广告