2 条题解

  • 0
    @ 2023-4-22 9:46:18
    #include<stdio.h>
    #include<stdlib.h>
    #include<iostream>
    #include<string.h>
    #define FORa(i,s,e) for(int i=s;i<=e;i++)
    #define FORs(i,s,e) for(int i=s;i>=e;i--)
    
    using namespace std;
    
    const int N=2000;
    string sta,stb;
    int m,n,f[N+1][N+1];//f[i][j]字符串sta(sta[0]-sta[i-1])转化到字符串stb(stb[0]-stb[j-1])的最短编辑距离
    inline int min(int a,int b){return a<b?a:b;}
    int main()
    {
    cin>>sta>>stb;
    n=sta.size(),m=stb.size();
    memset(f,127/3,sizeof(f));
    FORa(i,1,n) f[i][0]=i;
    FORa(i,1,m) f[0][i]=i;
    f[0][0]=0;//注意边界与初值,当两字符串中存在空串处理
    FORa(i,1,n)
    FORa(j,1,m)
    if(sta[i-1]==stb[j-1]) f[i][j]=f[i-1][j-1];//当当前字符相同 ,答案等于之前每个减一位的答案
    else f[i][j]=min(min(f[i-1][j-1],f[i-1][j]),f[i][j-1])+1;
    //f[i-1][j-1]表示把sta[i-1]改成stb[j-1] f[i-1][j]表示把字符串sta中的sta[i]删除 f[i][j-1]表示字符串sta后插入stb[j]
    printf("%d",f[n][m]);
    return 0;
    }
    
    • 0
      @ 2023-4-14 19:58:28

      wy

      • 1

      信息

      ID
      1407
      时间
      1000ms
      内存
      128MiB
      难度
      7
      标签
      递交数
      224
      已通过
      59
      上传者