Python程序：计算将字符串转换为相同字符串两次连接所需的运算次数

假设我们有一个小写字符串 s。现在考虑一个操作，我们可以删除、插入或更新 s 中的任何字符。我们需要计算将 s 转换为 (t 连接 t) 所需的最少操作次数，其中 t 是任何字符串。

因此，如果输入类似于 s = "pqrxqsr"，则输出将为 2，因为我们可以将 "x" 更新为 "p" 并删除 "s"，然后 s 为 "pqrpqr"，即 s = t 连接 t，其中 t = "pqr"。

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

  • 定义一个函数 edit_distance()。它将接收 s1 和 s2 作为参数。
  • m := s1 的大小
  • n := s2 的大小
  • cur := 从 0 到 n 的一个新列表
  • 对于范围从 0 到 m - 1 的 i，执行以下操作：
    • prev := cur
    • cur := 一个包含 (i + 1) 和 n 个 0 的列表
    • 对于范围从 0 到 n - 1 的 j，执行以下操作：
      • 如果 s1[i] 和 s2[j] 相同，则 cur[j + 1] := prev[j]，否则 cur[j + 1] := (cur[j]，prev[j]，prev[j + 1] 中的最小值) + 1
  • 返回 cur[n]
  • 从主方法中执行以下操作：
  • res := s 的大小
  • 对于范围从 0 到 s 的大小 - 1 的 i，执行以下操作：
    • res := edit_distance(s 从索引 0 到 i - 1 的子字符串，s 从索引 i 到末尾的子字符串) 和 res 中的最小值
  • 返回 res

示例

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

def solve(s):
   def edit_distance(s1, s2):
      m, n = len(s1), len(s2)
      cur = list(range(n + 1))
      for i in range(m):
         prev, cur = cur, [i + 1] + [0] * n
         for j in range(n):
            cur[j + 1] = (prev[j]
            if s1[i] == s2[j] else min(cur[j], prev[j], prev[j + 1]) + 1)
         return cur[n]

   res = len(s)
   for i in range(len(s)):
      res = min(edit_distance(s[:i], s[i:]), res)
   return res

s = "pqrxqsr"
print(solve(s))

输入

"pqrxqsr"

输出

None

更新于: 2021年10月18日

136 次浏览

开启您的 职业生涯

通过完成课程获得认证

立即开始
广告