首页 > 代码库 > 编程之美---计算字符串的相似度

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

对于不同的字符串,判断其相似程度。可以修改一个字符,增加一个字符,删除一个字符等操作。

分析:当两个字符串第一个字符相等时,直接把两个字符串跳到第二个位置开始比较就可以了。当两个字符串第一个字符不相等时,不管怎么操作总是,要么第一个串跳到第二个位置,第二个串位置不变;或者第一个串位置不变,第二个跳到第二个位置;或者两个串都跳到第二个位置(同过修改串的字符)。于是就可以写个递归程序处理。

 1 int calculateStringDistance(string strA, int pABegin, int pAEnd, string strB, int pBBegin, int pBEnd) 2  { 3      if(pABegin > pAEnd) 4      { 5          if(pBBegin > pBEnd) 6              return 0; 7          else 8              return pBEnd - pBBegin + 1; 9      }10 11      if(pBBegin > pBEnd)12      {13          if(pABegin > pAEnd)14              return 0;15          else16              return pAEnd - pABegin + 1;17      }18 19      if(strA[pABegin] == strB[pBBegin])20      {21          return calculateStringDistance(strA, pABegin+1, pAEnd, strB, pBBegin+1, pBEnd);22      }23      else24      {25          int t1 = calculateStringDistance(strA, pABegin, pAEnd, strB, pBBegin+1, pBEnd);26          int t2 = calculateStringDistance(strA, pABegin+1, pAEnd, strB, pBBegin, pBEnd);27          int t3 = calculateStringDistance(strA, pABegin+1, pAEnd, strB, pBBegin+1, pBEnd);28          return minValue(t1, t2, t3) + 1;29      }30  }
View Code

因为递归时,有些子问题重复了,所以可以增加一个数组来记录计算出的每一个值,每次调用时,直接查找有木有这个值,有就直接用,不要再计算了。

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