莫欺少年穷，修仙之旅在这开始—>算法基础课题解

思路：

1. f[i][j] 表示 a[1~i] 转换成 b[1~j] 的最少操作数
2. 状态转移有三种操作：删除，插入，替换
3. 删除：f[i-1][j] + 1
4. 插入：f[i][j-1] + 1
5. 替换：若a[i] == b[j]，则 f[i-1][j-1]；否则，f[i-1][j-1] + 1
6. 最后，f[i][j] = min{f[i-1][j] + 1, f[i][j-1] + 1, f[i-1][j-1] + (a[i] != b[j])}

完整代码

#include<bits/stdc++.h>

using namespace std;

const int N = 1010, M = 15;

int n,m;
char str[N][M];
int f[M][M];

// a 变成 b 的最少操作数
int edit_distance(char a[],char b[])
{
    int n=strlen(a+1),m=strlen(b+1); 

    for(int i=1;i<=n;i++) f[i][0]=i; //删除

    for(int i=1;i<=m;i++) f[0][i]=i; //插入

    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            f[i][j]=min(min(f[i-1][j],f[i][j-1])+1,f[i-1][j-1]+(a[i]!=b[j]));

    return f[n][m];
}

int main()
{
    cin>>n>>m;

    for(int i=0;i<n;i++) cin>>str[i]+1;

    while(m--)
    {
        char s[M];
        int k;
        cin>>s+1>>k;

        int res=0;
        for(int i=0;i<n;i++)
            if(edit_distance(str[i],s)<=k)
                res++;

        cout<<res<<endl;
    }

    return 0;
}