字符串编辑距离

前言

字符串编辑距离(Edit Distance)，是俄罗斯科学家Vladimir Levenshtein在1965年提出的概念，又称Levenshtein距离，是指两个字符串之间，由一个转成另一个所需的最少编辑操作次数。

算法介绍

判断2个字符串相似情况

枚举字符串S和T最后一个字符s[i]、t[j]对应的四种情况：(字符-字符)(字符-空白)(空白-字符)(空白-空白)；显然的是，(空白-空白)必然是多余的编辑操作。

第一种：

S空白，T字符b，S变成T，最后，在S的末尾插入“字符X”

dp[i,j] = dp[i,j-1] + 1

第二种：

S字符a，T字符b，S变成T，最后，将a修改成b

dp[i,j] = dp[i-1,j-1] + (X==Y ? 0 : 1)

第三种：

S字符a，T空白，S变成T，a被删除

dp[i,j] = dp[i-1,j] + 1

具体代码实现：

int lessEditDistance(char *source, char *target, int sLength, int tLength, int **dp) {
	int srcLength = sLength;
	int tarLength = tLength;

	for (int i = 1; i <= srcLength; i++) {
		dp[i][0] = i;
	}

	for (int j = 1; j <= tarLength; j++) {
		dp[0][j] = j;
	}

	for (int i = 1; i <= srcLength; i++) {
		for (int j = 1; j <= tarLength; j++) {
			if (source[i - 1] == target[j - 1]) {
				dp[i][j] = dp[i - 1][j - 1];
			}
			else {
				dp[i][j] = 1 + minTreeNum(dp[i - 1][j], dp[i - 1][j - 1], dp[i][j - 1]);
			}
		}
	}

	for (int i = 0; i <= srcLength; i++) {
		for (int j = 0; j <= tarLength; j++) {
			printf("dp[%d][%d]=%d  ", i, j, dp[i][j]);
		}
		printf("\n");
	}

	return dp[srcLength][tarLength];
}
           

参考资料：

七月算法：https://www.julyedu.com/