HJ52 计算字符串的编辑距离

本节目标：理解“HJ52 计算字符串的编辑距离”的核心思路，并能把它用于实际开发或面试表达。

说明：原 OneNote 中有图片引用，但图片未包含在导出目录中；本页保留了可用的文字与代码内容。 中等 通过率：31.88% 时间限制：1秒 空间限制：256M 知识点 ==字符串====动态规划== 描述 Levenshtein 距离，又称编辑距离，指的是两个字符串之间，由一个转换成另一个所需的最少编辑操作次数。许可的编辑操作包括将一个字符替换成另一个字符，插入一个字符，删除一个字符。编辑距离的算法是首先由俄国科学家 Levenshtein 提出的，故又叫 Levenshtein Distance 。

例如： 字符串A: abcdefg 字符串B: abcdef 通过增加或是删掉字符 ”g” 的方式达到目的。这两种方案都需要一次操作。把这个操作所需要的次数定义为两个字符串的距离。

要求： 给定任意两个字符串，写出一个算法计算它们的编辑距离。

数据范围：给定的字符串长度满足 1≤len(str)≤1000 输入描述： 每组用例一共2行，为输入的两个字符串 输出描述： 每组用例输出一行，代表字符串的距离 示例1 输入： abcdefgabcdef ==复制== 输出： 1

==思路====：==

• ==记录每一个源字符串的所有子串到目标字符串的所有子串的操作数；==
• ==最后一次的计算就是最大操作，因为我们从空子串一直遍历到等于字符串本身的子串；==
• ==由小子串逐步加====1== ==进行计算====，后面的可以利用前端的计算成果。== 编辑距离（Levenshtein 距离）是一种衡量两个序列差异的字符串度量，计算它们之间通过插入、删除、替换操作进行转换所需的最少操作数。计算编辑距离的一个常见方法是使用动态规划。这里是一个基于动态规划计算编辑距离的算法描述以及对应的Python代码实现： 计算两个字符串之间的 Levenshtein 距离（编辑距离）是一个经典的动态规划问题。我们将通过一个动态规划表来解决此问题，其中每个表项 dp[i][j] 代表从字符串 A 的前 i 个字符转换到字符串 B 的前 j 个字符所需的最少编辑操作次数。

动态规划表的构建：

1. 初始化阶段：
   1. 创建一个二维数组 dp，其中 dp[i][j] 表示 str1 的前 i 个字符转换到 str2 的前 j 个字符所需的最小编辑次数。
   2. 初始化表格的第一行和第一列。第一行表示从空字符串转换到 str2 的每个前缀的编辑次数，第一列表示从 str1 的每个前缀转换到空字符串的编辑次数。
2. 填表过程：
   1. 逐个填写 dp 表的每个格子。
   2. 如果当前字符相同（str1[i-1] == str2[j-1]），则当前格子的值即为左上角格子的值（无需编辑）。
   3. 如果不同，考虑三种操作（插入、删除、替换），取这三种操作的最小值加1作为当前格子的值。
3. 结果提取：
   1. 表格的最右下角的值 dp[m][n] 就是从 str1 全部转换到 str2 的最少编辑次数。

定义一个函数来计算两个字符串之间的 Levenshtein 距离

def levenshtein_distance(source, target):

计算输入的两个字符串的长度

source_len, target_len = len(source), len(target)

创建一个二维列表（矩阵）来记录从一个字符串转换到另一个字符串的操作次数

distance_matrix = [[0] * (target_len + 1) for _ in range(source_len + 1)]

初始化矩阵的第一列，这里的i代表source字符串的前i个字符变为空字符串需要的删除次数，索引0表示空字符

for i in range(source_len + 1): distance_matrix[i][0] = i

初始化矩阵的第一行，这里的j代表空字符串变为target字符串的前j个字符需要的插入次数

for j in range(target_len + 1): distance_matrix[0][j] = j

通过比较source和target的字符，填充整个矩阵

for i in range(1, source_len + 1): for j in range(1, target_len + 1):

如果当前对比的字符相同，那么这一位置的编辑距离就与左上角的位置相同

if source[i - 1] == target[j - 1]: distance_matrix[i][j] = distance_matrix[i - 1][j - 1] else:

如果字符不同，计算删除、插入或替换操作的最小编辑距离并加1

distance_matrix[i][j] = min( distance_matrix[i - 1][j] + 1, # 删除source的一个字符 distance_matrix[i][j - 1] + 1, # 向source插入target的一个字符 distance_matrix[i - 1][j - 1] + 1 # 替换source的字符为target的字符 )

返回最终的编辑距离，即将整个source字符串转换为整个target字符串的最小操作数

return distance_matrix[source_len][target_len]

给定两个字符串

input_source = "abc" input_target = "ac"

计算这两个字符串的编辑距离

edit_distance = levenshtein_distance(input_source, input_target)

输出计算结果

print(edit_distance) # 输出：1