Python 代码实现最少字符串编辑距离算法

Python 代码实现最少字符串编辑距离算法

字符串编辑距离是指两个字符串间的最小编辑次数，通常用于比较字符串的相似度。

编辑可以包括插入、删除和替换操作。

解题思路：

使用动态规划来解决最少字符串编辑距离问题。具体步骤如下：

1. 创建一个二维数组 dp，其中 dp[i][j] 表示字符串 s1 的前 i 个字符和字符串 s2 的前 j 个字符的最少编辑距离。

2. 初始化 dp 数组。当 s1 为空字符串时，将字符串 s2 转换成 s1 需要插入 s2 的所有字符，即 dp[0][j] = j（0 <= j <= len(s2)）。同理，当 s2 为空字符串时，将字符串 s1 转换成 s2 需要插入 s1 的所有字符，即 dp[i][0] = i（0 <= i <= len(s1)）。

3. 逐个计算 dp 数组的值。当 s1[i - 1] 等于 s2[j - 1] 时，即字符串 s1 的第 i 个字符和字符串 s2 的第 j 个字符相同时，不需要进行任何操作，此时 dp[i][j] 等于 dp[i - 1][j - 1]。否则，需要进行插入、删除或者替换操作，dp[i][j] 等于以下三种情况的最小值：

   1）插入操作：dp[i][j] = dp[i][j - 1] + 1

   2）删除操作：dp[i][j] = dp[i - 1][j] + 1

   3）替换操作：dp[i][j] = dp[i - 1][j - 1] + 1

4. 最终的最少字符串编辑距离即为 dp[len(s1)][len(s2)]。

代码实现如下：

def minEditDistance(s1, s2):
    m, n = len(s1), len(s2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    # 初始化dp数组
    for i in range(1, m + 1):
        dp[i][0] = i
    for j in range(1, n + 1):
        dp[0][j] = j
    # 计算dp数组的值
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i - 1] == s2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            else:
                dp[i][j] = min(dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1]) + 1
    return dp[m][n]

示例：

s1 = 'kitten'
s2 = 'sitting'
min_edit_distance = minEditDistance(s1, s2)
print(min_edit_distance) # 输出结果为3，即将'kitten'转换成'sitting'需要进行3次编辑操作。