最短编辑距离问题 Python
题目描述
给定 n个长度不超过 10的字符串以及 m 次询问,每次询问给出一个字符串和一个操作次数上限。
对于每次询问,请你求出给定的n 个字符串中有多少个字符串可以在上限操作次数内经过操作变成询问给出的字符串。
每个对字符串进行的单个字符的插入、删除或替换算作一次操作。
样例
3 2
abc
acd
bcd
ab 1
acbd 2
1
3
算法1
(动态规划) $O(n^2)$
状态表示f(i, j):把a[1,2, …, i]变到b[1, 2, …, j]的所有类操作次数的最小值
状态迁移: 按最后一步操作分类,分为四种
- 在最后一位操作: 分为增, 删, 改 分别为f[i, j - 1] + 1, f[i - 1, j] + 1 和 f[i - 1, j - 1] + 1
- 不在最后一位操作, f[i, j] = f[i - 1, j - 1]
代码里要注意的一个地方就是初始化,也就是处理边界的意思,考虑其中一个序列没有元素,全是增或删的操作
时间复杂度
$O(n^2)$, 分析和最长公共子序列一样,从子问题数量和转移耗费时间入手
Python 代码
n = int(input())
a = "0" + input()
m = int(input())
b = "0" + input()
f = [[0] * 1010 for i in range(1010)]
if __name__ == "__main__":
#边界情况处理,对应如果其中一个序列没有元素,全是增或全是删操作的情况
for i in range(m + 1):
f[0][i] = i
for j in range(n + 1):
f[j][0] = j
for i in range(1, n + 1):
for j in range(1, m + 1):
f[i][j] = min(f[i][j - 1], f[i -1][j]) + 1
if a[i] == b[j]:
f[i][j] = min(f[i][j], f[i - 1][j - 1])
else:
f[i][j] = min(f[i][j], f[i - 1][j - 1] + 1)
print(f[n][m])