编辑距离
日期:2014-05-01 23:53:29
最后更新日期:2015-10-04 19:43:50
1) 删除一个字符;
2) 添加一个字符;
3) 修改一个字符;
转变为另外一个字符串，所需要的最少操作数。
记两字符串长度分别为i和j，有如下动态规划的公式:
[code lang="cpp"]
case i = 0 且 j = 0，edit(i, j) = 0;
case i = 0 且 j > 0，edit(i, j) = j;
case i > 0 且 j = 0，edit(i, j) = i;
default:
edit(i, j) == min{ edit(i-1, j) + 1, edit(i, j-1) + 1, edit(i-1, j-1) + f(i, j) };
当第一个字符串的第i个字符不等于第二个字符串的第j个字符时，f(i, j) = 1；否则，f(i, j) = 0。
[/code]
举例:由"hello"变为"world",要么是"hell"转变为"world"时，删除一个字符'o'，或者是"hello"转变为"worl",增加一个字符"d"，也或者是"hell"转变为"worl"后，'o'变换为'd'。 这里观察第三式子，可以只用两个数组来缓冲中间结果即可。
算法实现:
[code lang="cpp"]
#include<iostream>
#include<vector>
#include<string>
using namespace std;
int min(int a,int b,int c)
{
int tmp=a>b?b:a;
return tmp>c?c:tmp;
}
int edit(string &a , string &b)
{
int m=a.size();
int n=b.size();
vector<int> d0(n+1,0);
vector<int> d1(n+1,0);
for(int i=1; i<=n; ++i) d1[i]=i;
for(int i=1; i<=m; ++i)
{
d0=d1;
for(int j=1; j<=n; ++j)
{
int x=d0[j]+1;
int y=d1[j-1]+1;
int tmp=a[i-1]==b[j-1]?0:1;
int z=d0[j-1]+tmp;
d1[j]=min(x,y,z);
}
}
return d1[n];
}
int main()
{
string a("hello"),b("world");
cout<<edit(a,b)<<endl;
return 0;
}
[/code]
PS:上诉不需要用两个数组,只需要一个临时变量。
[code lang="cpp"]
int edit(string &a , string &b)
{
int m=a.size();
int n=b.size();
vector<int> d0(n+1,0);
for(int i=1; i<=n; ++i) d0[i]=i;
for(int i=1; i<=m; ++i)
{
int z=i-1;
for(int j=1; j<=n; ++j)
{
int x=z;
y=j>1?d0[j-1]+1:i;
int tmp=a[i-1]==b[j-1]?0:1;
z=d0[j];
d0[j]=min(x+tmp,y+1,z+1);
}
}
return d0[n];
}
[/code]
计算矩阵为:
0 1 2 3 4
1 * * * *
2 * * * *
3 * * * *
4 * * * *
x z
y d[j]
参考:
1.http://www.cnblogs.com/biyeymyhjob/archive/2012/09/28/2707343.html