最小编辑距离

保护私人版权，尊重他人版权。转载请注明出处并附带页面链接

前言

全日制有一个规划中的小游戏，其最优解与最小编辑距离问题类似，所以把这个题翻了出来，炒炒冷饭。

题目来源

72. 编辑距离 https://leetcode-cn.com/problems/edit-distance/

算法描述

两种办法，dp和动态规划。但是，如果不出意外，dp会很慢，因为他测试样例有几个字符串长度几百的，最长的500。

假设有两个字符串A和B，如果A通过多次执行删除/替换/插入一个字符，最终可以变换为字符串B，则执行的次数就是编辑距离。

比如，存在字符串horse和ros

1. 替换r->h，ros->hos
2. 插入r，hos->hors
3. 插入e，horse

这样，我们就可以得知，horse最少需要通过3次操作才能变为ros。

我们如果希望用动态规划的办法去求解，则首先需要有一个初始状态和一个变化过程，并有一张表去记录这个初始状态和变化过程。

假设，有字符串str1和str2，长度分别为len1，和len2，则可以设置表distance[len1+1][len2+1]。用distance[i][j]表示截取str1长度i的子串与截取str2的长度为j的子串的匹配。这时，我们就可以轻易确定初始状态，distance[i][0]表示str1各个子串与str2的空子串编辑距离，distance[0][j]表示str2各个子串与str1的空子串编辑距离。初始状态如下表。

| | | r | o | s |
| ———— | ———— | ———— |
| | 0 | 1 | 2 | 3|
| h | 1 | | ||
| o | 2 | |||
| r | 3 | |||
| s | 4 | |||
| e | 5 | ||||

得到初始状态之后，就是确定变化过程了。题目已经明确要求，只允许三种操作。

1. 插入一个字符
2. 删除一个字符
3. 替换一个字符

假设当前步骤，我们执行上面任意一个步骤，就可以得到当前最小编辑距离，那么有以下三种情况。

1. 假设str1[0:i-1]通过插入一个字符可以与str2[0:j]匹配，则distance[i][j] = distance[i-1][j] +1

2. 假设str1[0:i]通过删除一个字符可以与str2[i:j-1]匹配，则distance[i][j] = distance[i][j-1] +1

3. 假设str1[i]!=str2[j]，则str1[0:i]通过替换一个字符可以与str2[0:j]匹配，则distance[i][j] = distance[i-1][j-1] +1

但是，要知道我们要求的是最小编辑距离。以上三种操作都能让我们得到distance[i][j]的值，但不一定是distance[i][j]的最小值，因此我们要取以上三种情况的最小值作为distance[i][j]的最小值。

按照这个步骤，从distance[1][1]一直遍历到distance[len1][len2]就能得到最终结果了。

代码

我直接按照上面的思路写的代码，有优化空间，百度很多，这里我不搬砖，但是按照我的了解，思路都是一样的，仅初始化过程不同的代码有明显差别。distance的取值过程是一样的。

class Solution {
public:
    int minDistance(string word1, string word2) {
        int len1 = word1.length(), len2 = word2.length(), i = 0, j = 0, up = 0, left = 0, upLeft = 0;
		// 编辑距离表
		int distance[501][501] = {0};
		// 初始化
		for (i = 0; i<= len1; i++) {
			for (j = 0; j <= len2; j++) {
				if (i == 0) {
					distance[i][j] = j;
				} else if (j == 0) {
					distance[i][j] = i;
				}
			}
		}
		// 计算
		for (i = 1; i<= len1; i++) {
			for (j = 1; j <= len2; j++) {
				up = distance[i-1][j] + 1;
				left = distance[i][j-1] + 1;
				upLeft = distance[i-1][j-1] + (word1[i-1] == word2[j-1] ? 0 : 1);
				distance[i][j] = up > left ? (left > upLeft ? upLeft : left) : (up > upLeft ? upLeft : up);
			}
		}
		return distance[len1][len2];
    }
};

算法应用

编辑距离实际上可以反应两个字符串的相似程度，类似的还有一个汉明距，他们在信息纠错、图像识别等多个领域都有应用，可以参考pHash算法（图像感知算法）， 这里面就用到了编辑距或汉明距判断图像相似度。
此外，有一点想法不知是否正确，如果这样求出来的是最小编辑距离，那么用较长的一个字符串其长度值减去这个最小编辑距离是否就是『最大匹配距离』，这个想法简单验证了几个字符串，似乎是合理的，但是样例不够全面，因此不敢定论。
更多扩展应用可以自行百度，欢迎交流。

Sub

扫码关注微信公众号，随时随地，掌握最新技术资讯

微信