【线性DP】编辑距离

题目

899. 编辑距离

---

给定 $n$ 个长度不超过 $10$ 的字符串以及 $m$ 次询问，每次询问给出一个字符串和一个操作次数上限。

对于每次询问，请你求出给定的 $n$ 个字符串中有多少个字符串可以在上限操作次数内经过操作变成询问给出的字符串。

每个对字符串进行的单个字符的插入、删除或替换算作一次操作。

输入格式

第一行包含两个整数 $n$ 和 $m$ 。

接下来 $n$ 行，每行包含一个字符串，表示给定的字符串。

再接下来 $m$ 行，每行包含一个字符串和一个整数，表示一次询问。

字符串中只包含小写字母，且长度均不超过 $10$ 。

输出格式

输出共 $m$ 行，每行输出一个整数作为结果，表示一次询问中满足条件的字符串个数。

数据范围

$1 \le n, m \le 1000$ ,

输入样例：

3 2
abc
acd
bcd
ab 1
acbd 2

输出样例：

1
3

解题

方法一：动态规划

思路

对于每一个查询字符串 b ，循环之前给出的 $n$ 个字符串 a ，对每对字符串做一次最短编辑距离的动态规划，统计出最短编辑距离小于上限次数的字符串的数量并输出。

代码

import java.util.*;
import java.io.*;

public class Main {
    static final int N = 1010;
    
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken();
        int n = (int) in.nval;
        in.nextToken();
        int m = (int) in.nval;
        List<char[]> lst = new ArrayList<>();
        for (int i = 0; i < n; ++i) {
            in.nextToken();
            lst.add((' ' + in.sval).toCharArray());
        }
        while (m-- > 0) {
            in.nextToken();
            char[] b = (' ' + in.sval).toCharArray();
            in.nextToken();
            int lmt = (int) in.nval;
            int bLen = b.length - 1;
            int cnt = 0;
            for (char[] a : lst) {
                int aLen = a.length - 1;
                int[][] dp = new int[aLen + 1][bLen + 1];
                for (int i = 0; i <= bLen; ++i) dp[0][i] = i;
                for (int i = 0; i <= aLen; ++i) dp[i][0] = i;
                for (int i = 1; i <= aLen; ++i) {
                    for (int j = 1; j <= bLen; ++j) {
                        dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + 1;
                        if (a[i] == b[j]) dp[i][j] = Math.min(dp[i][j], dp[i - 1][j - 1]);
                        else dp[i][j] = Math.min(dp[i][j], dp[i - 1][j - 1] + 1);
                    }
                }
                if (dp[aLen][bLen] <= lmt) ++cnt;
            }
            System.out.println(cnt);
        }
    }
}

#include <iostream>
#include <cstring>

using namespace std;

const int N = 1010;
int n, m;
char as[N][N], b[N];
int dp[N][N];

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; ++i) scanf("%s", as[i] + 1);
    while (m--) {
        int lmt;
        scanf("%s%d", b + 1, &lmt);
        int bl = strlen(b + 1);
        int cnt = 0;
        for (int i = 0; i < n; ++i) {
            char* a = as[i];
            int al = strlen(a + 1);
            for (int i = 0; i <= bl; ++i) dp[0][i] = i;
            for (int i = 0; i <= al; ++i) dp[i][0] = i;
            for (int i = 1; i <= al; ++i) {
                for (int j = 1; j <= bl; ++j) {
                    dp[i][j] = min(min(dp[i - 1][j], dp[i][j - 1]) + 1, dp[i - 1][j - 1] + (a[i] != b[j]));
                }
            }
            if (dp[al][bl] <= lmt) ++cnt;
        }
        printf("%d\n", cnt);
    }
    
    return 0;
}