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

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 = 1010f = [[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)

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。