程序员面试金典-面试题01.05-一次编辑

古城微笑少年丶 2022-12-31 12:28 205阅读 0赞

## 程序员面试金典-面试题01.05-一次编辑 ##

本题可以转化为求编辑距离。题目限定为可以**插入、删除、替换**一个字符，这种编辑距离称为**莱温斯坦距离**，同样经常遇到的还有**汉明距离**等。

字符串有三种编辑操作:插入一个字符、删除一个字符或者替换一个字符。 给定两个字符串，编写一个函数判定它们是否只需要一次(或者零次)编辑。
    
     
    
    示例 1:
    
    输入: 
    first = "pale"
    second = "ple"
    输出: True
     
    
    示例 2:
    
    输入: 
    first = "pales"
    second = "pal"
    输出: False
    
    来源：力扣（LeetCode）
    链接：https://leetcode-cn.com/problems/one-away-lcci
    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

算法根据下图所示递推公式实现：  
![在这里插入图片描述][20201229190215734.png_pic_center]  
具体解法如下：

int edit_distance(char *, char *);
    int min_two(int, int);
    int min_three(int, int, int);
    bool oneEditAway(char* first, char* second){
        
        int distance = edit_distance(first,second);
        if(distance<2)
            return true;
        else
            return false;
    }
    int edit_distance(char * first, char * second)
    {
        
        int len_first = strlen(first);
        int len_second = strlen(second);
        int d[len_first+1][len_second+1];
        int i=0,j=0,cost=0;
        for(i=0;i<(len_first+1);i++)
        {
        
            d[i][0]=i;
        }
        for(j=0;j<(len_second+1);j++)
        {
        
            d[0][j]=j;
        }
        for(i=1;i<(len_first+1);i++)
        {
        
            for(j=1;j<(len_second+1);j++)
            {
        
                if(first[i-1]==second[j-1]){
        
                    cost=0;
                }
                else{
        
                    cost=1;
                }
                d[i][j]=min_three(
                    d[i-1][j]+1,
                    d[i][j-1]+1,
                    d[i-1][j-1]+cost
                );
            }
        }
        return d[len_first][len_second];
    }
    int min_two(int a,int b)
    {
        
        if(a<b)
            return a;
        else
            return b;
    }
    int min_three(int a,int b,int c)
    {
        
        int d = min_two(a,b);
        return min_two(d,c);
    }

[20201229190215734.png_pic_center]: /images/20221120/fd69a0386ff44cfcbfbace1f3e45d450.png