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))
输入
"pqrxqsr"
输出
None