编程之美系列之计算字符串的相似度

1、在给定的位置插入字符

2、将当前字符替换成任意字符

3、删除任意字符

题目分析：

如果当前两个字符相等，则结果就是Src+1和Pattern+1两个字符串的最小操作数。

如果不等，就分三种情况：

1、如果是在给定的位置插入字符，那要求的操作数就是Src和Pattern+1两个字符串的最小操作数

2、如果将当前字符替换，那要求的操作数就是Src+1和Pattern+1两个字符串的最小操作数3、如果是删除Src的当前字符，则要求的操作数就是Src+1和Pattern两个字符串的最小操作数

最终结果就是上面三种情况中最小的操作数+1.

递归解法：程序很容易就可以写出来，递归的出口就是某一个字符串到达串尾，则距离就是没有到达串尾的那个字符串的长度。

非递归的解法：就是动态规划，假设dp[i][j]表示Src从第i个字符开始与Pattern从第j个字符开始所求得的最小操作数，动态规划递推的式子如下：

if Src[i] != Pattern[j], dp[i][j] = min(dp[i][j + 1], dp[i + 1][j + 1], dp[i +1][j];

else, dp[i][j] = dp[i + 1][j + 1];

使用动态规划需要注意的地方：

1、递推式中只出现了后面的数据，所以递推的时候应该是从后到前。

2、注意递推时的边界条件的处理。

核心参考代码如下：

 

//递归解法  
int CalStr(const char* Src, const char *Pattern)  
{  
    assert(Src && Pattern);  
    if(*Src == '\0')  
    {  
        return strlen(Pattern);  
    }  
    if(*Pattern == '\0')  
    {  
        return strlen(Src);  
    }  
    if(*Src == *Pattern)  
    {  
        return CalStr(Src + 1, Pattern + 1);  
    }  
    int t1 = CalStr(Src, Pattern + 1);//插入字符  
    int t2 = CalStr(Src + 1, Pattern + 1);//替换字符  
    int t3 = CalStr(Src + 1, Pattern);//删除字符  
    return min(t1, t2, t3) + 1;  
}  
//非递归解法，动态规划  
int CalStrDP(const char *Src, const char *Pattern)  
{  
    assert(Src && Pattern);  
    memset(dp, 0, sizeof(int) * Max_N * Max_N);  
    int nLen1 = strlen(Src);  
    int nLen2 = strlen(Pattern);  
    int i,j;  
    for(i = nLen1 - 1; i >= 0; --i)  
    {  
        for(j = nLen2 - 1; j >= 0; --j)  
        {  
            if(Src[i] == Pattern[j])  
            {  
                dp[i][j] = dp[i + 1][j + 1];  
            }  
            else  
            {  
                if(i < nLen1 - 1 || j < nLen2 - 1)//如果在两个字符串的末尾，则默认初始值为0，直接计算  
                {             
                    if(i + 1 >= nLen1)//设置边界值  
                    {  
                        dp[i + 1][j + 1] = Max_N;  
                        dp[i + 1][j] = Max_N;  
                    }  
                    if(j + 1 >= nLen2)//设置边界值  
                    {  
                        dp[i][j + 1] = Max_N;  
                        dp[i + 1][j + 1] = Max_N;  
                    }  
                }  
                dp[i][j] = min(dp[i][j + 1], dp[i + 1][j + 1], dp[i + 1][j]) + 1;  
            }  
        }  
    }  
    return dp[0][0];  
}  

 

 

下面给出main函数和辅助函数：

 

 

#include<stdio.h>  
#include<string.h>  
#include<assert.h>  
const int Max_N = 100;  
int dp[Max_N][Max_N];  
  
inline int min(const int a, const int b, const int c)  
{  
    int t = a < b ? a : b;  
    return t < c ? t : c;  
}  
  
int main()  
{  
    char Src[Max_N];  
    char Pattern[Max_N];  
    while(gets(Src) && gets(Pattern))  
    {  
        printf("递归：%d\n", CalStr(Src, Pattern));  
        printf("非递归：%d\n", CalStrDP(Src, Pattern));  
    }  
    return 0;  
}  

 

 

 

补充：软件开发 , C++ ,