用 Python 编写程序，查找最少删除操作以使字符串成为字符串

pythonserver side programmingprogramming更新于 2026/1/18 15:08:17

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

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

为了解决这个问题，我们将遵循以下步骤 −

m := size of s
n := size of 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))