题目描述
//来自算法基础课
这个题就是对最短编辑距离问题 的简单应用啦
这个问题模型我在这里不再赘述了
如果没有听过的同学们戳这里
假设你已经会做上面那道题了
对于这道题
我们发现这题多跑几遍最短编辑距离就行了吧
然后我们来算一发时间复杂度
1e6 * 10^2 = 1e8
时限两秒,是ok的
那就这么做吧简单暴力
(其实正解就是这么做的)
代码码
#include<bits/stdc++.h>
using namespace std;
const int N = 15;
const int M = 1001;
int n,m,f[N][N];
char s[M][N];
int edit_dis(char a[],char b[]) {
int lena = strlen(a+1);
int lenb = strlen(b+1);
for(register int i=1; i<=lena; i++) f[i][0] = i;
for(register int i=1; i<=lenb; i++) f[0][i] = i;
for(register int i=1; i<=lena; i++)
for(register int j=1; j<=lenb; j++) {
f[i][j] = min(f[i-1][j]+1 , f[i][j-1]+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);
}
return f[lena][lenb];
}
int main(){
scanf("%d%d",&n,&m);
for(register int i=0; i<n; i++) scanf("%s",s[i]+1);
while(m--) {
char q[N];
int limit;
scanf("%s%d",q+1,&limit);
int ans = 0;
for(register int i=0; i<n; i++)
if(edit_dis(s[i],q)<=limit) ans++;
printf("%d\n",ans);
}
return 0;
}
请问为什么这么写过不了?
这里s[i]为什么要加一,而下面的s[i]又不需要加一,有点被搞乱了
要留一个位置0,要不然i,j为0时没法从上一个状态转移(毕竟没有-1),而且i,j表示第几个字母也很人性,容易看懂