计算在 Python 中将字符串作为同一字符串连接两次所需的操作数的程序

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

所以，如果输入像 s = "pqrxqsr"，那么输出将是 2，因为，我们可以用 "p" 更新 "x" 并删除 "s"，那么 s 是 "pqrpqr"，这是 s = t 连接 t，因为 t = "pqr"。

示例

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

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