编辑距离

题目 编辑距离

思路分析

和上题一样 这次是问有多少个能达到规定范围内

所以就是做多次最短编辑距离

代码实现

#include<bits/stdc++.h>

using namespace std;

const int N = 1e1 + 5, M = 1e3 + 10, INF = 2e9;

int n, m;

char str[M][N];

int f[N][N];

int edit_distance(char a[], char b[])

{

    int la = strlen(a + 1), lb = strlen(b + 1);

    for(int i=1;i<=la;i++)

        for(int j=1;j<lb;j++)

            f[i][j]=INF;

    for(int i=0;i<=la;i++)

        f[i][0] = i;

    for(int i=0;i<=lb;i++)

        f[0][i] = i;

    for(int i=1;i<=la;i++)

    {

        for(int j=1;j<=lb;j++)

        {

            f[i][j]=min(f[i-1][j],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()

{

    cin>>n>>m;

    for(int i=0;i<n;i++)

        cin>>(str[i] + 1);

    while (m--)

    {

        int res = 0;

        char s[N];

        int limit;

        cin>>(s + 1)>>limit;

        for(int i=0;i<n;i++)

            if(edit_distance(str[i], s)<=limit)

                res++;

        cout<<res<<endl;

    }

    return 0;

}

同类题型

视频讲解

⬅️ 非递减子序列拓展思路 🏠 00-刷题理模型 ➡️ 线性dp