当前位置:编程学习 > C/C++ >>

求字符串编辑距离

这道题,我在阿里巴巴面试的时候碰到了,google的笔试题。。。
 
设A和B是2个字符串。要用最少的字符操作将字符串A转换为字符串B。这里所说的字符操作包括:
(1)删除一个字符;
(2)插入一个字符;
(3)将一个字符改为另一个字符。
将字符串A变换为字符串B所用的最少字符操作数称为字符串A到B的编辑距离,记为d(A,B)。试设计一个有效算法,对任给的2个字符串A和B,计算出它们的编辑距离d(A,B)。
方法1:编程之美的递归方法
 
#include <iostream>  
#include <string>  
using namespace std;  
  
int Min(int a,int b,int c)  
{  
    int t = a<b?a:b;  
    return t<c?t:c;  
}  
  
int CalDistance(const string &strA,int pAbegin,int pAend,  
                const string &strB,int pBbegin,int pBend)  
{  
    if(pAbegin>pAend){  
        if(pBbegin>pBend)return 0;  
        else return pBend-pBbegin+1;  
    }  
    if(pBbegin>pBend){  
        if(pAbegin>pAend)return 0;  
        else return pAend-pAbegin+1;  
    }  
    if(strA[pAbegin] == strB[pBbegin]){  
        return CalDistance(strA,pAbegin+1,pAend,strB,pBbegin+1,pBend);  
    }  
    else{  
        int disa = CalDistance(strA,pAbegin+1,pAend,strB,pBbegin+1,pBend) + 1;//替换  
        int disb = CalDistance(strA,pAbegin,pAend,strB,pBbegin+1,pBend) + 1;//a插入  
        int disc = CalDistance(strA,pAbegin+1,pAend,strB,pBbegin,pBend) + 1;//b插入  
        return Min(disa,disb,disc);  
    }  
}  
int main()  
{  
    string strA = "lsjd";  
    string strB = "ls";  
    cout<<CalDistance(strA,0,strA.size()-1,strB,0,strB.size()-1)<<endl;  
    system("pause");  
    return 0;  
}  

 

 
上面这种方法有个缺点:递归树上有重复计算的节点。我们可以通过备忘录的方法来记录一些值,从而降低重复计算。
 
方法2:动态规划解法
  总结个经验:像这种从后面由前面推(自顶向下)都可以转换为动态规划算法(自底向上)。包括本博客上:斐波拉契序列,完全背包问题,捞鱼问题。
    我们可以得出这样一段动态规划公式:(下面的内容引自:http://qinxuye.me/article/get-edit-distance-by-dynamic-programming/;http://blog.chinaunix.net/uid-20761674-id-75042.html)
 
  (1)如果i == 0 且 j == 0,edit(i, j)=0
 
  (2)如果i == 0 且 j > 0,edit(i, j)=j
 
  (3)如果i > 0 且j == 0,edit(i, j)=i(2、3点之前已经陈述)
 
  (4)如果0 < i≤1  且 0 < j ≤ 1 ,edit(i, j) == min{ edit(i-1, j) + 1, edit(i, j-1) + 1, edit(i-1,j-1)+ f(i, j) },这里当字符串1的第i个字符不等于字符串2的第j个字符时,f(i, j) = 1;否则,f(i, j) = 0。
 
  (5)如果i > 1且 j > 1时,这个时候可能出现操作(4),由之前的推导,我们只能交换一次,否则就没有意义。这个时候在比较最小值中可能加入edit(i-2, j-2) +1,什么时候加入呢?假设i-2长度的字符串1子串和j-2长度的字符串2子串已经得出最优解,这个时候如果s1[i-1] == s2[j] 并且s1[i] == s2[j-1],这时就在比较值中加入edit(i-2, j-2) + 1(这个1是交换一次的操作)
 
     即最后的递推公式:首先给定第一行和第一列,然后,每个值d[i,j]这样计算:d[i][j]   =   min(d[i-1][j]+1,d[i][j-1]+1,d[i-1][j-1]+(s1[i] ==  s2[j]?0:1));   
 
 代码:
 
#include <stdio.h>     
#include <string.h>     
char s1[1000],s2[1000];     
int min(int a,int b,int c) {     
    int t = a < b ? a : b;     
    return t < c ? t : c;     
}     
void editDistance(int len1,int len2) {     
    int d[len1+1][len2+1];   //这里其实要动态分配  
    int i,j;     
    for(i = 0;i <= len1;i++)     
        d[i][0] = i;   //i从第1个开始,表示第1个字母,所以第0个没算  
    for(j = 0;j <= len2;j++)     
        d[0][j] = j;     
    for(i = 1;i <= len1;i++)     
        for(j = 1;j <= len2;j++) {     
            int cost = s1[i] == s2[j] ? 0 : 1;     
            int deletion = d[i-1][j] + 1;     
            int insertion = d[i][j-1] + 1;     
            int substitution = d[i-1][j-1] + cost;     
            d[i][j] = min(deletion,insertion,substitution);     
        }     
    printf("%d\n",d[len1][len2]);     
}  

 


补充:软件开发 , C++ ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,