问题描述：见BOP（编程之美） 3.3
这里除了给出效率比较低的递归版本之外，还给出了效率比较高的递归的备忘录版本和递推版本，时间和空间复杂度都是O(n^2)，在递归的备忘录版本和递推版本中，我们定义两个字符串为strA和strB，长度分别为size_A和size_B，C[i,j]为子串strA[i],strA[i+1],...,strA[size_A-1]和 strB[i],strB[i+1],...,strB[size_B-1]的编辑距离，那么状态转移方程为：
C[i,j]=0 if i=size_A and j=size_B
C[i,j]=size_B-j if i=size_a and j<size_B
C[i,j]=size_A-i if i<size_a and j=size_B
C[i,j]=C[i+1,j+1] if strA[i]=str[j]
C[i,j]=min{C[i+1,j],C[i,j+1],C[i+1,j+1]}+1 if strA[i]!=str[j]
代码如下：
//求两个字符串的编辑距离问题
//递归版本，无备忘录
int editDistance(char *strA,int A_beg,int A_end,char *strB,int B_beg,int B_end){
if(A_beg>A_end){
if(B_beg>B_end)
return 0;
else
return B_end-B_beg+1;
}
if(B_beg>B_end){
if(A_beg>A_end)
return 0;
else
return A_end-A_beg+1;
}
if(strA[A_beg]==strB[B_beg]){
return editDistance(strA,A_beg+1,A_end,strB,B_beg+1,B_end);
}else{
int a=editDistance(strA,A_beg+1,A_end,strB,B_beg+1,B_end);
int b=editDistance(strA,A_beg+1,A_end,strB,B_beg,B_end);
int c=editDistance(strA,A_beg,A_end,strB,B_beg+1,B_end);
return min(a,b,c)+1;
}
}
int min(int a,int b,int c){
if(a<=c && a<=b)
return a;
else if(b<=c && b<=a)
return b;
else
return c;
}
//求两个字符串的编辑距离问题
//递归版本，备忘录C[i,j]表示strA[i]...strA[size_A-1]与strB[j]...strB[size_B-1]的编辑距离
int editDistance_mem(char *strA,int size_A,char *strB,int size_B){
int **C=new int*[size_A+1];
for(int i=0;i<=size_A;i++){
C[i]=new int[size_B+1]();
}
//初始化
for(int i=0;i<=size_A;i++){
for(int j=0;j<=size_B;j++)
C[i][j]=INT_MAX;
}
int res=EDM(C,strA,0,size_A-1,strB,0,size_B-1);
//free mem
for(int i=0;i<=size_A;i++){
delete [] C[i];
}
delete [] C;
return res;
}
int EDM(int **C,char *strA,int i,int A_end,char *strB,int j,int B_end){
if(C[i][j]<INT_MAX)//做备忘
return C[i][j];
if(i>A_end){
if(j>B_end)
C[i][j]=0;
else
C[i][j]=B_end-j+1;
}else if(j>B_end){
if(i>A_end)
C[i][j]=0;
else
C[i][j]=A_end-i+1;
}
else if(strA[i]==strB[j])
C[i][j]=EDM(C,strA,i+1,A_end,strB,j+1,B_end);
else{
int a=EDM(C,strA,i+1,A_end,strB,j+1,B_end);
int b=EDM(C,strA,i,A_end,strB,j+1,B_end);
int c=EDM(C,strA,i+1,A_end,strB,j,B_end);
C[i][j]=min(a,b,c)+1;
}
return C[i][j];
}
//求两个字符串的编辑距离问题
//递推版本 C[i,j]表示strA[i]...strA[size_A-1]与strB[j]...strB[size_B-1]的编辑距离
int editDistance_iter(char *strA,int size_A,char *strB,int size_B){
int **C=new int*[size_A+1];
for(int i=0;i<=size_A;i++){
C[i]=new int[size_B+1]();
}
for(int i=size_A;i>=0;i--){
for(int j=size_B;j>=0;j--){
if(i>size_A-1){
if(j>size_B-1)
C[i][j]=0;
else
C[i][j]=size_B-j;
}else if(j>size_B-1){
if(i>size_A-1)
C[i][j]=0;
else
C[i][j]=size_A-i;
}else if(strA[i]==strB[j])
C[i][j]=C[i+1][j+1];
else
C[i][j]=min(C[i+1][j+1],C[i+1][j],C[i][j+1])+1;
}
}
int res=C[0][0];
//free mem
for(int i=0;i<=size_A;i++){
delete [] C[i];
}
delete [] C;
return res;
}