一、问题描述
设A和B是两个字符串。要用最少的字符操作将字符串A转换为字符串B。这里所说的字符操作包括：
二、分析解答
设所给的两个字符串为A[1:m]和B[1:n]。定义D[i][j]=d(A[1:i],B[1,j])。单字符a,b间的距离定义为：
d(a,b)=0 (a=b)
d(a,b)=1(a!=b)
考察从字符串A[1:i]到字符串B[1:j]的变换。可分成以下几种情况：
（1）字符A[i]改为字符B[j]；需要d(A[i],B[j])次操作。
（2）删除字符A[i]；需要1次操作。
（3）插入字符B[j]；需要1次操作。
因此，D[i][j]可递归地计算如下。
D[i][j]=min{D[i-1][j-1]+d(A[i],B[j]),D[i-1][j]+1,D[i][j-1]+1}。
三、算法描述
int dist(A[0…m-1],B[0…n-1])
{
int D[0…m,0…n]
int i,j,cost
对于i等于0至m
D[i, 0]=i
对于j等于0至n
D[0,j]=j
对于i等于1至m
返回d[m,n]
}
四、代码实现
定义一个二维数组D[][]存储中间结果，如下图所示，为已经初始化后的情况。然后从D[1,1]开始从左到右，从上到下依次按填表，表的最后一个元素D[m,n]就是要求的最终结果。
|
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
|
0 |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
|
1 |
1 |
|
|
|
|
|
|
|
2 |
2 |
|
|
|
|
|
|
|
3 |
3 |
|
|
|
|
|
|
|
4 |
4 |
|
|
|
|
|
|
|
5 |
5 |
|
|
|
|
|
|
|
6 |
6 |
|
|
|
|
|
|
#include<iostream>
#include<string>
using namespace std;
int D[100][100];
int dis[100];
int min(int a,int b,int c)
{
return c<(a>b?b:a)?c:(a>b?b:a);
}
int dist(char * A,char * B)
{
int m=strlen(A);
int n=strlen(B);
int i,j;
for(i=0;i<=m;++i)
{
D[i][0]=i;
}
for(j=0;j<=n;++j)
{
D[0][j]=j;
}
int cost;
for(i=1;i<=m;++i)
{
for(j=1;j<=n;++j)
{
if(A[i-1]==B[j-1])
cost=0;
else
cost=1;
D[i][j]=min(D[i-1][j-1]+cost,D[i-1][j]+1,D[i][j-1]+1);
}
}
return D[m][n];
}
int dist2(char * A,char * B)
{
int m=strlen(A);
int n=strlen(B);
int i,j;
for(i=0;i<=n;++i)
dis[i]=i;
int cost;
for(i=1;i<=m;++i)
{
int y=i-1;
for(j=1;j<=n;++j)
{
int x=y;
y=dis[j];
int z=j>1?dis[j-1]:i;
cost=A[i-1]==B[j-1]?0:1;
dis[j]=min(x+cost,y+1,z+1);
}
}
return dis[n];
}
int main(int argc, char* argv[])
{
char * ch1="bcdefghijklmnopq";
char * ch2="abcdefghijklmnopadfsafwe";
cout<<dist(ch1,ch2)<<endl;
cout<<dist2(ch1,ch2)<<endl;
return 0;
}
package net.hr.algorithm.stroper;
/**
* 字符串编辑距离
*
* 这是一种字符串之间相似度计算的方法。
* 给定字符串S、T，将S转换T所需要的插入、删除、替代操作的数量叫做S到T的编辑路径。
* 其中最短的路径叫做编辑距离。
*
* 这里使用了一种动态规划的思想求编辑距离。
*
* @author heartraid
*
*/
public class StrEditDistance {
/**字符串X*/
private String strX="";
/**字符串Y*/
private String strY="";
/**字符串X的字符数组*/
private char[] charArrayX=null;
/**字符串Y的字符数组*/
private char[] charArrayY=null;
public StrEditDistance(String sa,String sb){
this.strX=sa;
this.strY=sb;
}
/**
* 得到编辑距离
* @return 编辑距离
*/
public int getDistance(){
charArrayX=strX.toCharArray();
charArrayY=strY.toCharArray();
return editDistance(charArrayX.length-1,charArrayY.length-1);
}
/**
* 动态规划解决编辑距离
*
* editDistance(i,j)表示字符串X中[0.... i]的子串 Xi 到字符串Y中[0....j]的子串Y1的编辑距离。
*
* @param i 字符串X第i个字符
* @param j 字符串Y第j个字符
* @return 字符串X(0...i)与字符串Y(0...j)的编辑距离
*/
private int editDistance(int i,int j){
if(i==0&&j==0){
//System.out.println("edit["+i+","+j+"]="+isModify(i,j));
return isModify(i,j);
}
else if(i==0||j==0){
if(j>0){
//System.out.println("edit["+i+","+j+"]=edit["+i+","+(j-1)+"]+1");
if(isModify(i,j) == 0) return j;
return editDistance(i, j-1) + 1;
}
else{
//System.out.println("edit["+i+","+j+"]=edit["+(i-1)+","+j+"]+1");
if(isModify(i,j) == 0) return i;
return editDistance(i-1,j)+1;
}
}
else {
//System.out.println("edit["+i+","+j+"]=min( edit["+(i-1)+","+j+"]+1,edit["+i+","+(j-1)+"]+1,edit["+(i-1)+","+(j-1)+"]+isModify("+i+","+j+")");
int ccc=minDistance(editDistance(i-1,j)+1,editDistance(i,j-1)+1,editDistance(i-1,j-1)+isModify(i,j));
return ccc;
}
}
/**
* 求最小值
* @param disa 编辑距离a
* @param disb 编辑距离b
* @param disc 编辑距离c
*/
private int minDistance(int disa,int disb,int disc){
int dismin=Integer.MAX_VALUE;
if(dismin>disa) dismin=disa;
if(dismin>disb) dismin=disb;
if(dismin>disc) dismin=disc;
return dismin;
}
/**
* 单字符间是否替换
*
* isModify(i,j)表示X中第i个字符x(i)转换到Y中第j个字符y(j)所需要的操作次数。
* 如果x(i)==y(j)，则不需要任何操作isModify(i, j)=0； 否则，需要替换操作，isModify(i, j)=1。
* @param i 字符串X第i个字符
* @param j 字符串Y第j个字符
* @return 需要替换，返回1；否则，返回0
*/
private int isModify(int i,int j){
if(charArrayX[i]==charArrayY[j])
return 0;
else return 1;
}
/**
* 测试
* @param args
*/
public static void main(String[] args) {
System.out.println("编辑距离是："+new StrEditDistance("eeba","abac").getDistance());
}
}
五、优化方法
从上面算法可以看出，该算法时间复杂性为0(m*n),空间复杂性为O（m*n）。同时可以看出，当对第i行进行填表时，只需要用到第i-1行的数据，因此可以用一个一维数组dis[0…n]代替二维数组D[0…m,0…n]，因此空间复杂性降为O(n)。实现代码如上面函数dist2()所示。