用 Python 编写程序，计算将字符串拼接成两次相同字符串所需的操作数

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

假设我们有一个小写字符串 s。现在考虑一个操作，我们可以删除、插入或更新 s 中的任何字符。我们必须计算使 s = (t 拼接 t) 所需的最少操作数，适用于任何字符串 t。

因此，如果输入为 s = "pqrxqsr"，则输出将为 2，因为我们可以用 "p" 更新 "x"并删除"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]、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))