编程之美3.3 计算两个字符串的相似度

      假如有两个字符串分别是：abcd，bbcd，那么，这两个字符串不相同的字符个数是1，即第一个字符时不相同的，定义字符串的相似度为 1 / (x + 1)，其中，x 就是不相同的字符个数。

      我们可以有三种方法比较两个字符串中不相同字符的个数：

      1.去掉第一个字符串中不相同的那个字符，并同时再去比较下一个字符

      2.去掉第二个字符串中不相同的那个字符，并同时再去比较下一个字符

      3.同时去掉字符串中不相同的那个字符，并同时再去比较下一个字符

      之后，我们需要把不相同的字符个数加 1 ，最后，我们只需要取得三种方法中值最小的那个即可。

      很容易发现，依次比较字符是否相同时时递归的操作，所以，这道题目解法如下：

      函数声明：

/*3.3 计算两个字符串的相似度*/
int DutCalculateStringDistance(std :: string&, std :: string&);
int DutCalculateStringDistance(std :: string&, int, int, std :: string&, int, int);

      源代码：

int DutCalculateStringDistance(string& s1, int begin1, int end1, string& s2, int begin2, int end2)
{
if (begin1 > end1)
{
if (begin2 > end2)
return 0;
else
return end2 - begin2 + 1;
}
if (begin2 > end2)
{
if (begin1 > end1)
return 0;
else
return end1 - begin1 + 1;
}
if (s1[begin1] == s2[begin2])
return DutCalculateStringDistance(s1, begin1 + 1, end1, s2, begin2 + 1, end2);
else
{
/*计算各个不同办法的相似度*/
int t1 = DutCalculateStringDistance(s1, begin1 + 1, end1, s2, begin2, end2);
int t2 = DutCalculateStringDistance(s1, begin1, end1, s2, begin2 + 1, end2);
int t3 = DutCalculateStringDistance(s1, begin1 + 1, end1, s2, begin2 + 1, end2);
/*取一个最小的相似度*/
return DutMin<int>(t1, t2, t3) + 1;
}
}
int DutCalculateStringDistance(string& s1, string& s2)
{
return DutCalculateStringDistance(s1, 0, (int)s1.length() - 1, s2, 0, (int)s2.length() - 1);
}

      代码中用到的模板函数：

template <typename T>
T DutMin(T data1, T data2)
{
return data1 < data2 ? data1 : data2;
}

template <typename T>
T DutMin(T data1, T data2, T data3)
{
return DutMin<T>(DutMin<T>(data1, data2), data3);
}

最后

以上就是现实乌冬面为你收集整理的编程之美3.3 计算两个字符串的相似度的全部内容，希望文章能够帮你解决编程之美3.3 计算两个字符串的相似度所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。