AcWing 899. 编辑距离

题目传送门

一、理解与感悟

多次使用最小编辑距离模板，反复使用之，最短编辑距离的时间复杂度是\(n^2\),本题的\(n\)上限是\(10\),就是\(100\)。

一共有\(n<=1000\)个，\(m<=1000\)次询问,所以算法复杂度是\(10^2 * 10^3 * 10^3=10^8\),本题的时间要求是\(2\)秒，还是可以完成的。

二、实现代码

#include <bits/stdc++.h>

using namespace std;
const int N = 15;
const int M = 1010;

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

int edit_distance(char a[], char b[]) {
    int la = strlen(a + 1), lb = strlen(b + 1);
    for (int i = 0; i <= lb; i++) f[0][i] = i;
    for (int i = 0; i <= la; i++) f[i][0] = i;
    for (int i = 1; i <= la; i++)
        for (int j = 1; j <= lb; j++) {
            f[i][j] = min(f[i - 1][j] + 1, f[i][j - 1] + 1);
            f[i][j] = min(f[i][j], f[i - 1][j - 1] + (a[i] != b[j]));
        }
    return f[la][lb];
}

int main() {
    //优化输入
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 0; i < n; i++) cin >> (str[i] + 1);
    while (m--) {
        char s[N];
        int limit;
        cin >> (s + 1) >> limit;
        int res = 0;
        for (int i = 0; i < n; i++)
            if (edit_distance(str[i], s) <= limit) res++;
        printf("%d\n", res);
    }
    return 0;
}