3.3 计算字符串的相似度
问题：
给定任意两个字符串，修改、增加、删除方式让他们变得相同，最少步骤。
解决：
递归解决，一步操作后，将下面三种情况变成相同字符串
1. A[2, ... , end] 和 B[1, ... , end]
2. A[1, ... , end] 和 B[2, ... , end]
3. A[2, ... , end] 和 B[2, ... , end]
代码如下：
#include <stdio.h>#include <stdlib.h>#include <string.h>int min(int t1, int t2, int t3){ int temp = 0; if (t1 > t2) temp = t2; else temp = t1; if(temp > t3) return t3; else return temp;}int calculateStrDistance(char* strA, int pABegin, int pAEnd, char* strB, int pBBegin, int pBEnd){ if(pABegin > pAEnd) { if(pBBegin > pBEnd) return 0; else return pBEnd - pBBegin + 1; } if(pBBegin > pBEnd) { if(pABegin > pAEnd) return 0; else return pAEnd - pABegin + 1; } if(strA[pABegin] == strB[pBBegin]) { return calculateStrDistance(strA, pABegin + 1, pAEnd, strB, pBBegin + 1, pBEnd); } else { int t1 = calculateStrDistance(strA, pABegin, pAEnd, strB, pBBegin + 1, pBEnd); int t2 = calculateStrDistance(strA, pABegin + 1, pAEnd, strB, pBBegin, pBEnd); int t3 = calculateStrDistance(strA, pABegin + 1, pAEnd, strB, pBBegin + 1, pBEnd); return min(t1, t2, t3) + 1; }}int main(){ char* strA = "abcdef"; char* strB = "abcdefg"; int pABegin = 0; int pAEnd = 5; int pBBegin = 0; int pBEnd = 6; printf("The distance is %d\n", calculateStrDistance(strA, pABegin, pAEnd, strB, pBBegin, pBEnd)); return 0;}