我认为在这种情况下，更深入地了解算法很重要。除了向您提供一些伪代码外，我还将向您介绍该算法的基本步骤，并向您展示所需的数据如何在最终的矩阵中“编码”。当然，如果您不需要滚动自己的算法，那么您显然应该使用其他人的算法，如MattH建议的那样！
大图景
在我看来，这类似于Wagner-
Fischer算法的实现。基本思想是计算“附近”前缀之间的距离，取最小值，然后从中计算出当前字符串对的距离。例如，假设您有两个字符串
'i'和
'h'。让我们沿着矩阵的垂直和水平轴进行布局，如下所示：
_ h_ 0 1i 1 1
此处，
'_'表示空字符串，矩阵中的每个单元格对应于一个将输入（
''或
'i'）输入到输出（
''或
'h'）的编辑序列。
空字符串到长度为L的任何字符串的距离为L（需要插入L个字符）。从任何长度为L的字符串到空字符串的距离也为L（需要删除L个字符）。这覆盖了第一行和第一列中的值，这些值只是递增。
从那里，您可以通过从上，左和左上值中取最小值，然后加上一个值来计算任何位置的值，或者，如果字符串中该点的字母相同，则取上一个值-
left值不变。对于上
(1, 1)表中的at值，最小值是
0at
(0, 0)，所以at值
(1,1)是
1，这是从
'i'到的最小编辑距离
'h'（一次替换）。因此，通常，最小编辑距离始终位于矩阵的右下角。
现在，与做比较
is，再做一次
hi。这里再一次，矩阵中的每个单元对应于取得输入（编辑序列
''，
'i'或
'is'）到输出（
''，
'h'，或
'hi'）。
_ h i_ 0 1 2i 1 1 #s 2 # #
我们首先放大矩阵，将其
#用作尚不知道的值的占位符，然后通过递增来扩展第一行和第一列。这样，我们就可以开始计算
#上面标记位置的结果。让我们从
(2,1)（行（列），即行主要表示法）开始。在上，左上和左值中，最小值为
1。表中对应的字母不同-
s和
h-因此我们在该最小值上加一个以获得
2并继续。
_ h i_ 0 1 2i 1 1 #s 2 2 #
让我们继续到的值
(1, 2)。现在情况有所不同，因为表中的对应字母是相同的-它们都是
i。这意味着我们可以选择在左上角的单元格中取值
而无需添加一个
。这里的指导直觉是，我们不必增加计数，因为在此位置将相同的字母添加到两个字符串中。而且由于两根弦的长度都增加了一个，所以我们沿对角线移动。
_ h i_ 0 1 2i 1 1 1s 2 2 #
在最后一个空单元格之后，一切恢复正常。对应的字母是
s和
i，因此我们再次取最小值并加一个，得到
2：
_ h i_ 0 1 2i 1 1 1s 2 2 2
如果我们继续此过程并以
is和
hi-开头的两个较长单词
isnt（忽略标点符号）和
hint：
_ h i n t_ 0 1 2 3 4i 1 1 1 2 3s 2 2 2 2 3n 3 3 3 2 3t 4 4 4 3 2
这个矩阵稍微复杂一点，但是这里的最终最小编辑距离仍然是
2，因为这两个字符串的最后两个字母相同。方便！
重新创建编辑顺序
那么我们如何从该表中提取编辑类型呢？关键是要意识到桌子上的移动对应于特定的编辑类型。因此，例如，从
(0, 0)到的向右移动
(0, 1)会将我们从
_-> _，不需要编辑，到
_ -> h，需要一个编辑，插入。同样，从
(0, 0)到的向下移动
(1, 0)会将我们从
_ ->_，不需要任何编辑，到
i -> _，需要一个编辑，删除。最后，从
(0, 0)到的对角线运动
(1, 1)使我们从
_ ->_，不需要任何编辑，到
i -> h，需要一个编辑，一次替换。
因此，现在我们要做的就是反转步骤，从上，左和左上单元格中追踪局部最小值回到原点，请
(0,0)记住，如果当前值与最小值相同，则我们必须移至左上角的单元格，因为这是唯一一种不会增加编辑距离的移动。
这是您可以采取的步骤的详细说明。从完成的矩阵的右下角开始，重复以下操作，直到到达左上角：
- 查看左上方的相邻单元格。如果不存在，请转到步骤3。如果该单元格确实存在，请记下该位置存储的值。
- 左上单元格中的值等于当前单元格中的值吗？如果是这样，请执行以下操作：
- 记录一个空操作（即
Equal
）。在这种情况下，不需要编辑，因为此位置的字符相同。 - 更新当前单元格，向上和向左移动。
- 返回步骤1。
- 记录一个空操作（即
- 这里有很多分支：
- 如果左侧没有单元格，而上方没有单元格，则您位于左上角，算法已完成。
- 如果左侧没有单元格，请转到步骤4。（此操作将继续循环直到您到达左上角。）
- 如果上方没有单元格，请转到步骤5。（此操作将循环进行，直到到达左上角。）
- 否则，请在左侧的单元格，左上方的单元格和上方的单元格之间进行三向比较。选择一个值最小的。如果有多个候选人，则可以随机选择一个。它们在此阶段 均 有效。（它们对应于具有相同总编辑距离的不同编辑路径。）
- 如果选择了上面的单元格，请转到步骤4。
- 如果您选择左侧的单元格，请转到步骤5。
- 如果您在左上方选择单元格，请转到步骤6。
- 你正在上升。请执行下列操作：
- 在当前单元格上记录输入字符的删除。
- 更新当前单元格，向上移动。
- 返回步骤1。
- 您正在向左移动。请执行下列操作：
- 记录当前单元格上输出字符的插入。
- 更新当前单元格，向左移动。
- 返回步骤1。
- 您正在对角移动。请执行下列操作：
- 在当前单元格上记录输入字符的替换，以代替当前单元格上的输出字符。
- 更新当前单元格，向上和向左移动。
- 返回步骤1。
把它放在一起
在上面的示例中，有两种可能的路径：
(4, 4) -> (3, 3) -> (2, 2) -> (1, 2) -> (0, 1) -> (0, 0)
和
(4, 4) -> (3, 3) -> (2, 2) -> (1, 1) -> (0, 0)
扭转它们，我们得到
(0, 0) -> (0, 1) -> (1, 2) -> (2, 2) -> (3, 3) -> (4, 4)
和
(0, 0) -> (1, 1) -> (2, 2) -> (3, 3) -> (4, 4)
因此，对于第一个版本，我们的第一个操作是向右移动，即插入。插入的字母是
h，因为我们要从
isnt移到
hint。（这与
Insert,h您的详细输出相对应。）我们的下一个操作是对角线移动，即替换或无操作。在这种情况下，这是无操作的，因为两个位置的编辑距离是相同的（即字母是相同的）。这样
Equal,i,i。然后向下移动，对应于删除。删除的字母是
s，因为我们再次从
isnt移到
hint。（通常，要插入的字母来自输出字符串，而要删除的字母来自输入字符串。）所以是
Delete,s。然后两个对角线运动，其值没有变化：
Equal, n, n和
Equal, t, t。
结果：
Insert, hEqual, i, iDelete, sEqual, n, nEqual, t, t
在以下位置执行这些说明
isnt：
isnt (No change)hisnt (Insertion)hisnt (No change)hint (Deletion)hint (No change)hint (No change)
总编辑距离为2。
我将保留第二条最小路径作为练习。请记住，两条路径是完全等效的。它们可能有所不同，但是它们将导致相同的最小编辑距离2，因此可以完全互换。在向后浏览矩阵的任何时候，如果您看到两个不同的局部最小值，则可以取其中一个，并且保证最终结果是正确的
一旦您掌握了所有这些内容，就不难编写代码了。在这种情况下，关键是要首先 深刻理解算法 。完成此操作后，对其进行编码就很容易了。
积累与重建
最后一点，您可以选择在填充矩阵时 累积 编辑内容。在这种情况下，矩阵中的每个单元格都可以是一个元组：
(2, ('ins', 'eq', 'del','eq', 'eq'))。您将增加长度， 并追加与从最小先前状态开始的移动相对应的操作。这样就消除了回溯，从而降低了代码的复杂性；但是会占用额外的内存。如果执行此操作，则最终编辑序列将与最终编辑距离一起出现在矩阵的右下角。
