Python程序以计算操纵次数使字符串成为同一字符串连接的两倍

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

因此，如果输入为s =“pqrxqsr”，则输出将为2，因为我们可以使用“p”更新“x”并删除“s”，然后s为“pqrpqr”，对于t =“pqr”，此处s = t concatenate t。

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

定义函数edit_distance()。这将获取s1，s2
m：s1的大小
n：s2的大小
cur：从0到n的新列表
对于范围内的i从0到m-1，执行以下操作
- prev：cur
- cur：由（i + 1）和n个0组成的列表
- 对于范围内的j从0到n – 1，执行以下操作
  - 如果s1 [i]和s2 [j]相同，则cur [j + 1] = prev [j]，否则为(cur[j]，prev[j]，prev[j + 1])的最小值+1
返回cur [n]
从主方法中执行以下操作−
res：s的大小
对于范围内的i从0到s的大小-1，执行以下操作
- res：s的i到末尾的子字符串和s的子字符串的距离的最小值的最小值
返回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))