侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 551 篇文章
  • 累计创建 117 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

【线性DP】编辑距离

GabrielxD
2022-11-29 / 0 评论 / 0 点赞 / 19 阅读 / 776 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2022-12-01,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

899. 编辑距离


给定 nn 个长度不超过 1010 的字符串以及 mm 次询问,每次询问给出一个字符串和一个操作次数上限。

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

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

输入格式

第一行包含两个整数 nnmm

接下来 nn 行,每行包含一个字符串,表示给定的字符串。

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

字符串中只包含小写字母,且长度均不超过 1010

输出格式

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

数据范围

1n,m10001 \le n, m \le 1000 ,

输入样例:

3 2
abc
acd
bcd
ab 1
acbd 2

输出样例:

1
3

解题

方法一:动态规划

思路

对于每一个查询字符串 b ,循环之前给出的 nn 个字符串 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;
}
0

评论区