设A和B是两个字符串,求将字符串A转换为字符串B的最少操作次数。字符操作共有如下三种:
(1)删除一个字符。
(2)插入一个字符。
(3)将一个字符改为另一个字符。
如A = “kitten”、 B = “sitting“,求编辑距离。
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<iomanip>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include <functional>
using namespace std;
typedef long long ll;
int i,j;
int dp[101][101]={{0}};
string a,b;
main()
{
cin >> a >> b;
for(i=0;i<=a.size();i++){
dp[i][0]=i;
}
for(i=0;i<=b.size();i++){
dp[0][i]=i;
}
for(i=1;i<=a.size();i++){
for(j=1;j<=b.size();j++){
if(a[i-1]==b[j-1]){
dp[i][j]=dp[i-1][j-1];
}
else{
dp[i][j]=min(dp[i-1][j],dp[i-1][j-1]);
dp[i][j]=min(dp[i][j],dp[i][j-1])+1;
}
}
}
cout << dp[a.size()][b.size()] << "\n";
}
标签:字符,include,int,距离,编辑,long,101,字符串,动态
From: https://blog.csdn.net/2301_78848414/article/details/143427313