问题
许多程序会大量使用字符串。对于不同的字符串,我们希望能够有办法判断其相似程度。我们定义了一套操作方法来把两个不相同的字符串变得相同,具体的操作方法为:
1.修改一个字符(如把“a”替换为“b”)。
2.增加一个字符(如把“abdd”变为“aebdd”)。
3.删除一个字符(如把“travelling”变为“traveling”)。
比如,对于“abcdefg”和“abcdef”两个字符串来说,我们认为可以通过增加/减少一个“g“的方式来达到目的。上面的两种方案,都仅需要一次操作。把这个操作所需要的次数定义为两个字符串的距离,给定任意两个字符串,写出一个算法来计算出它们的距离
分析
目前正在实习这家公司的笔试题,当时拿到题,就感觉似曾相识。回学校后,翻了翻之前的学习资料,在牛客网的算法面试题中找到了原型。它的确是一道经典的dp,其处理问题的方式,也是dp的常用套路。
编辑距离,又称Levenshtein距离,是指两个字串之间,由一个转成另一个所需的最少编辑操作次数,如果它们的距离越大,说明它们越是不同。
假设当前有两个字符串,它们分别是str1和str2。dp[i][j]的含义:str2("0->i")通过操作变成str1("0->j")的编辑距离
考虑以下三种情况str2("0->i")与str1("0->j-1")相同
,在末尾增加一个str1[j]字符,故此时dp[i][j] = dp[i][j-1] + 1;str2("0->i-1")与str1("0->j")相同
,在末尾删除一个str2[i]字符,故此时dp[i][j] = dp[i-1][j] + 1;str2("0->i-1")与str1("0->j-1")相同
,根据str2[i]与str1[j]的相等情况,分别考虑。str2[i]等于str1[j]时
,无需任何操作,故此时dp[i][j] = dp[i-1][j-1];str2[i]不等于str1[j]时
,替换str2[i]字符为str1[j]字符,故此时dp[i][j] = dp[i-1][j-1] + 1;
根据上面的讨论,我们可以看到dp[i][j]的值依赖它左上角的3个dp值
。在程序的开始阶段,我们应首先计算得到最不需要依赖的dp值
,也就是整个dp二维数组中的第一行与第一列。
int minValue(int a, int b, int c)
{
int t = a <= b ? a:b;
return t <= c ? t:c;
}
int calculateStringDistance(string strA, string strB)
{
int lenA = (int)strA.length();
int lenB = (int)strB.length();
//二维数组的内存分配,dp为一个数组指针
int **dp = new int*[lenA];
for (int i = 0; i < lenA; i++)
{
dp[i] = new int[lenB];
}
//初始化不需要依赖的dp值
for(int i = 0; i < lenA; i++) dp[i][0] = i;
for(int j = 0; j < lenB; j++) dp[0][j] = j;
dp[0][0] = 0;
//根据dp依赖的三种情况,从(1,1)位置处开始计算dp值
for(int i = 1; i < lenA; i++)
{
for(int j = 1; j < lenB; j++)
{
if(strB[j-1] == strA[i-1])
dp[i][j] = dp[i-1][j-1];
else
dp[i][j] = minValue(dp[i][j-1], dp[i-1][j], dp[i-1][j-1]) + 1;
}
}
int ret = dp[lenA-1][lenB-1];
//释放内存空间,先释放dp[i]的内存,再释放dp
for(int i = 0; i < lenA; i++)
delete [] dp[i];
delete []dp;
return ret;
}
int main()
{
string A = "abcdefg";
string B = "abcdef";
cout <<calculateStringDistance(A, B) << endl;
}
编辑距离的应用
小规模的字符串近似搜索,类似于搜索引擎中输入关键字,出现类似的结果列表,具体实现细节,有兴趣可以移步字符串近似搜索,进行更多的了解。