最短编辑距离

题目链接

/*
 * @Author: YMYS
 * @Date: 2024-02-25 21:38:22
 * @LastEditTime: 2024-12-22 12:45:30
 * @FilePath: \VScode-C&C++-Coding\Acwing\算法基础课\5.第五章\2.线性DP\5.最短编辑距离.cpp
 * @URL:https://www.acwing.com/problem/content/904/
 * @Description: 902. 最短编辑距离
 * 
 * 注意：这道最短编辑距离的题，是对字符串a进行更改，而不是对b改
 * 
 * 处理完边界问题后，我们遍历矩阵是从1往后遍历，所以我们只考虑两个字符串的末尾情况：
 * 1、末尾删除
 * 2、末尾插入
 * 3.1、修改末尾字符，并且a和b的末尾字符不相等
 * 3.2、修改末尾字符，并且a和b的末尾字符相等
 * 
 */
#include<bits/stdc++.h>

using namespace std;

const int N = 1010;

int n,m;
string a,b;
int f[N][N];//操作次数矩阵

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

    //先处理矩阵中a为空或者b为空的情况
    for(int i = 0;i<=m;i++) f[0][i] = i;//b有几个字符，a就添加几个

    for(int j=0;j<=n;j++) f[j][0] = j;//a有几个字符，a就自己删除几个

    //处理过0的边界，所以可以直接从1开始遍历
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            f[i][j] = min(f[i-1][j] + 1, f[i][j-1] + 1);

            //实质上这里的min在比较“删除”、“增加”、“修改”这三种操作哪个最少
            //只是我们这里的if条件判断的作用是：根据“末尾字符相不相等”这种情况，“修改”操作要不要加1
            //PS：因为我们的字符串是从0开始存的，但是我们遍历矩阵是从1开始遍历的，所以因该对a[]和b[]数组的下标都减一
            if(a[i-1] == b[j-1]) f[i][j] = min(f[i][j], f[i-1][j-1]);
            else f[i][j] = min(f[i][j], f[i-1][j-1] + 1 );

        }
    }

    cout<<f[n][m]<<endl;

    return 0;
}

编辑距离

题目链接

 /*
 * @Author: YMYS
 * @Date: 2024-09-03 18:02:23
 * @LastEditTime: 2024-12-22 17:49:34
 * @FilePath: \VScode-C&C++-Coding\Acwing\算法基础课\5.第五章\2.线性DP\6.编辑距离.cpp
 * @URL:https://www.acwing.com/problem/content/901/
 * @Description: 这道题就是“模拟题目”+“最短编辑距离”，注意别漏掉a[0]和b[0]即可
 */
#include<bits/stdc++.h>

using namespace std;

const int N = 1010;//字符串个数
const int M = 15;//字符串长度

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

int fa(string a, string b){
    int la = a.length();
    int lb = b.length();

    //初始化边界
    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++){
            int tmp = min(f[i-1][j], f[i][j-1]) + 1;

            //PS：
            //因为我们的字符串是从0开始存的，
            //但是我们遍历矩阵是从1开始遍历的，
            //所以因该对a[]和b[]数组的下标都减1
            //防止漏掉a[0]、b[0]
            if(a[i-1] == b[j-1]) f[i][j] = min(tmp,f[i-1][j-1]);
            else f[i][j] = min(tmp, f[i-1][j-1]+1);
        }
    }

    return f[la][lb];
}

int main()
{
    cin>>n>>m;
    for(int i=0;i<n;i++){
        cin>>str[i];
    }

    while (m--)
    {
        string ss;
        int limit = 0;
        cin>>ss>>limit;

        int res = 0;//str[][]数组中满足条件的字符串个数
        for(int i=0;i<n;i++){
            if(fa(str[i], ss) <= limit){
                res ++;
            }
        }

        cout<<res<<endl;
    }

    return 0;
}