这个题和活动 - AcWing编辑距离 差不多可以参考一下
只不过只能进行删除和修改操作 ；； 而我们的目标其实是修改操作 所以我们减去删除长度也就是本来字符串的长度差值就是我们要求的最终要修改的长度 ；
//编译代码不做过多解释，有疑问复习以下上面编译距离的题 #include<iostream> #include<cstring> #include<algorithm> using namespace std ; const int N = 1010 , INF = 1e9 ; char a[N] ,b[N] ; int f[N][N] ;//表示前i个字母由前j个字母转化的最少操作数 int main(){ scanf("%s" , a + 1 ) ; scanf("%s" , b + 1 ) ; int n = strlen(a + 1) ; int m = strlen(b + 1) ; for(int i = 0 ; i <= n ; i++){ for(int j = 0 ; j <= m ; j ++){ f[i][j] = 1000000 ; } } for(int i = 0 ; i <= n ; i ++ )f[i][0] = i ; for(int j = 0 ; j <= m ; j ++) f[0][j] = j ; for(int i = 1 ; i <= n ; i ++ ){ for(int j = 1 ; j <= m ; j ++ ){ f[i][j] = f[i-1][j] + 1 ;//只能进行删除操作 if(a[i] == b[j]) 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] - n + m << endl ; return 0 ; }
