首页 > 代码库 > 编程之美---计算字符串的相似度
编程之美---计算字符串的相似度
对于不同的字符串，判断其相似程度。可以修改一个字符，增加一个字符，删除一个字符等操作。
分析：当两个字符串第一个字符相等时，直接把两个字符串跳到第二个位置开始比较就可以了。当两个字符串第一个字符不相等时，不管怎么操作总是，要么第一个串跳到第二个位置，第二个串位置不变；或者第一个串位置不变，第二个跳到第二个位置；或者两个串都跳到第二个位置（同过修改串的字符）。于是就可以写个递归程序处理。
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 }
因为递归时，有些子问题重复了，所以可以增加一个数组来记录计算出的每一个值，每次调用时，直接查找有木有这个值，有就直接用，不要再计算了。
编程之美---计算字符串的相似度
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。