题目描述
899.编辑距离
给定 n
个长度不超过 10
的字符串以及 m
次询问,每次询问给出一个字符串和一个操作次数上限。
对于每次询问,请你求出给定的 n
个字符串中有多少个字符串可以在上限操作次数内经过操作变成询问给出的字符串。
每个对字符串进行的单个字符的插入、删除或替换算作一次操作。
样例
cin>>
3 2
abc
acd
bcd
ab 1
acbd 2
cout<<
1
3
算法1
(dp) $O(n^2)$
还是dp先继承,然后分两种情况,一种是一样的不变,一种是不一样要加1
时间复杂度
参考文献
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N = 10 + 9, M = 1e3 + 9;
char str[M][N];
int dp[N][N];
int edit_distance(char a[], char b[]){
int la = strlen(a + 1), lb = strlen(b + 1);
for(int i = 0; i <= la; i++) dp[i][0] = i;
for(int i = 0; i <= lb; i++) dp[0][i] = i;
for(int i = 1; i <= la; i++)
for(int j = 1; j <= lb; j++){
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] + (a[i] != b[j]));
}
return dp[la][lb];
}
int main(void){
int n, m;
cin >> n >> m;
for(int i = 0; i < n; i++) cin >> str[i] + 1;
while(m--){
char st[N];
int limit, answer = 0;
cin >> st + 1 >> limit;
for(int i = 0; i < n; i++)
if(edit_distance(str[i], st) <= limit)
answer++;
cout << answer << endl;
}
return 0;
}