899. 编辑距离（线性DP&最短编辑距离模板题）

文章目录

• ​​Question​​
• ​​Ideas​​
• ​​Code​​

Question

给定 n 个长度不超过 10 的字符串以及 m 次询问，每次询问给出一个字符串和一个操作次数上限。

对于每次询问，请你求出给定的 n 个字符串中有多少个字符串可以在上限操作次数内经过操作变成询问给出的字符串。

每个对字符串进行的单个字符的插入、删除或替换算作一次操作。

输入格式
第一行包含两个整数 n 和 m。

接下来 n 行，每行包含一个字符串，表示给定的字符串。

再接下来 m 行，每行包含一个字符串和一个整数，表示一次询问。

字符串中只包含小写字母，且长度均不超过 10。

输出格式
输出共 m 行，每行输出一个整数作为结果，表示一次询问中满足条件的字符串个数。

数据范围
1≤n,m≤1000,

输入样例：
3 2
abc
acd
bcd
ab 1
acbd 2
输出样例：
1
3

Ideas

同最短编辑距离

Code

# 线性DP 编辑距离模板题
n,m = list(map(int,input().split()))

lis = []
for i in range(n):
lis.append(input().strip())

N = 1010
f = [[0 for i in range(N)] for j in range(N)] # 代表所有让a[1-i]与b[1-j]相等的操作的最少次数

def edit_distance(a,b):
a = '0' + a
b = '0' + b
len_a,len_b = len(a)-1,len(b)-1

for i in range(1,len_a+1):
f[i][0] = i
for j in range(1,len_b+1):
f[0][j] = j

for i in range(1,len_a+1):
for j in range(1,len_b+1):
f[i][j] = min(f[i-1][j]+ 1,f[i][j-1]+ 1)
f[i][j] = min(f[i-1][j-1]+(a[i]!=b[j]),f[i][j])

return f[len_a][len_b]


for j in range(m):
b,limit = input().strip().split()
limit = int(limit)
cnt = 0
for i in range(n):
if edit_distance(lis[i],b) <= limit:
cnt += 1
print(cnt)