一、问题描述
设A和B是两个字符串。要用最少的字符操作将字符串A转换为字符串B。这里所说的字符操作包括：
（1）删除一个字符；
（2）插入一个字符；
（3）将一个字符改为另一个字符；
将字符串A变换为字符串B所用的最少字符操作数称为字符串A到B的编辑距离，记为d(A,B)。试设计一个有效算法，对任给的两个字符串A和B，计算出它们的编辑距离d(A,B)。
#include <iostream>
#include <algorithm>
const int MAXLEN =100;
#define Match 1
#define Insert 2
#define Delete 3
class EditDistance
{
typedef struct Cell
{
int cost;
int parant;
}cell_t;
public:
EditDistance()
{
memset(m,0,sizeof(int)*MAXLEN*MAXLEN);
for(int i=1;i!=MAXLEN;i++){
m[i][0].cost=i;
m[i][0].parant=Insert;
m[0][i].cost=i;
m[0][i].parant=Insert;
}
m[0][0].parant=-1;
}
//m[i][j]=min{m[i-1][j-1]+match(s[i],[j]),m[i][j-1]+1,m[i-1][j]+1}
int excute(char* s,char* t)
{
int opt[4];
int len_s=strlen(s);
int len_t=strlen(t);
for(int i=1;i!=len_s;i++){
for(int j=1;j!=len_t;j++){
opt[Match]=m[i-1][j-1].cost+match(s[i],t[j]);
opt[Insert]=m[i][j-1].cost+1;
opt[Delete]=m[i-1][j].cost+1;
m[i][j].cost=std::min(std::min(opt[Match],opt[Insert]),opt[Delete]);
}
}
return m[len_s-1][len_t-1].cost;
}
~EditDistance()
{
}
private:
int match(char i,char j)
{
if(i==j){
return 0;
}
return 1;
}
cell_t m[MAXLEN][MAXLEN];
};
int main()
{
char s[]="asdffd";
char t[]="aedfad";
EditDistance distance;
int res=distance.excute(s,t);
std::cout<<res<<std::endl;
getchar();
}