2 条题解
-
0陈烨鑫 (chenyexin) LV 10 @ 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; }
-
02023-4-14 19:58:28@
wy
- 1
信息
- ID
- 1407
- 时间
- 1000ms
- 内存
- 128MiB
- 难度
- 7
- 标签
- 递交数
- 224
- 已通过
- 59
- 上传者