899. 编辑距离
摘要
Title: 899. 编辑距离
Tag: LIS模型、dp
Memory Limit: 64 MB
Time Limit: 1000 ms
Powered by:NEFU AB-IN
899. 编辑距离
-
题意
给定 n 个长度不超过 10 的字符串以及 m 次询问，每次询问给出一个字符串和一个操作次数上限。
对于每次询问，请你求出给定的 n 个字符串中有多少个字符串可以在上限操作次数内经过操作变成询问给出的字符串。
每个对字符串进行的单个字符的插入、删除或替换算作一次操作。 -
思路
将最短编辑距离多次运用即可
-
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35'''
Author: NEFU AB-IN
Date: 2022-03-07 17:56:44
FilePath: \ACM\Acwing\899.py
LastEditTime: 2022-03-07 18:07:16
'''
N = 20
INF = int(2e9)
dp = [[INF] * N for _ in range(N)]
n, m = map(int, input().split())
s = [0]
for i in range(n):
s.append(" " + input())
for k in range(m):
b, x = input().split()
b = " " + b
x = int(x)
res = 0
for kk in range(1, n + 1):
a = s[kk]
for i in range(len(a)):
dp[i][0] = i
for i in range(len(b)):
dp[0][i] = i
for i in range(1, len(a)):
for j in range(1, len(b)):
dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1)
dp[i][j] = min(dp[i][j],
dp[i - 1][j - 1] + (1 if a[i] != b[j] else 0))
if dp[len(a) - 1][len(b) - 1] <= x:
res += 1
print(res)