Python 程序计算两个字符串之间的编辑距离

两个字符串之间的编辑距离衡量的是将一个字符串转换为另一个字符串所需的最小操作次数。可以执行各种操作，包括单个字符的插入、删除和替换。编辑距离也称为Levenshtein距离或最小编辑距离。

计算两个字符串之间编辑距离的算法

1. 初始化一个2D数组`dp`，其维度为(m+1) x (n+1)，其中m和n是两个字符串的长度。
2. 分别用从0到n和从0到m的值初始化`dp`的第一行和第一列。
3. 循环遍历`dp`的其余单元格：
   1. 如果两个字符串中当前位置的字符相同，则将`dp[i][j]`设置为`dp[i-1][j-1]`的值。
   2. 否则，将`dp[i][j]`设置为以下值的最小值
      1. `dp[i-1][j] + 1` (删除)
      2. `dp[i][j-1] + 1` (插入)
      3. `dp[i-1][j-1] + 1` (替换)
4. 两个字符串之间的编辑距离为`dp[m][n]`。

实现此算法的Python代码

输出

3
8

说明

在第一个例子中，"kitten"和"sitting"之间的编辑距离是3。我们可以通过将"k"替换为"s"，将"e"替换为"i"，并在末尾插入"g"来将"kitten"转换为"sitting"。

在第二个例子中，"rosettacode"和"raisethysword"之间的编辑距离是8。我们可以通过删除"o"，将"c"替换为"i"，将"d"替换为"s"，将"e"替换为"t"，在"t"之后插入"h"来将"rosettacode"转换为"raisethysword"。

时间复杂度

• 嵌套循环遍历2D数组dp的所有单元格。外层循环运行m+1次，内层循环运行n+1次。因此，嵌套循环的时间复杂度为O(mn)。
• 内层循环执行的操作都是常数时间操作。

因此，函数edit_distance()的总体时间复杂度为O(mn)。

空间复杂度

• 2D数组dp的空间复杂度为(m+1) x (n+1)。

因此，函数edit_distance()的空间复杂度为O(mn)。

在Python中计算两个字符串之间编辑距离还有其他方法。以下是一些

• 带备忘录的递归方法：在此方法中，我们可以使用递归来计算两个字符串之间的编辑距离。我们可以将每个子问题的结果存储在备忘录表中，以便在遇到相同子问题时重用该结果。在最坏情况下，此方法的时间复杂度为O(mn)，其中m和n是两个字符串的长度。

例如

输出

3

• 使用滚动数组的迭代方法：在此方法中，我们可以使用迭代方法来计算两个字符串之间的编辑距离。我们可以使用滚动数组来仅存储备忘录表的上一行，而不是整个表。此方法将空间复杂度降低到O(n)，其中n是较短字符串的长度。在最坏情况下，时间复杂度保持为O(mn)。

例如

输出

3

• 使用NumPy：NumPy是一个流行的用于数值计算的Python库。它提供了高效优化的数组操作函数。我们可以使用numpy库来实现编辑距离算法。在最坏情况下，此方法的时​​间复杂度为O(mn)，空间复杂度为O(mn)。

例如

输出

3

注意：NumPy方法在时间和空间复杂度方面与第一种方法类似，但它使用NumPy库的内置函数提供了一种有效执行矩阵操作的方法。

• 一种这样的方法是使用动态规划。

在动态规划中，我们创建一个矩阵，其中每个单元格代表两个子字符串之间的编辑距离。我们首先用从0到n的递增值初始化第一行和第一列，其中n是字符串的长度。然后，我们遍历矩阵中的其余单元格，并使用以下公式填充它们

最终答案将位于矩阵的最后一个单元格，即dp[n][n]。

例如

输出

3