U627380 字符串编辑距离

编辑距离（Levenshtein距离）是指将一个字符串转换成另一个字符串所需的最少操作次数。允许的操作包括： 1.插入一个字符 2.删除一个字符 3.替换一个字符 给定两个字符串 A 和 B，请计算它们之间的编辑距离。1.

第一行包含字符串 A 第二行包含字符串 B

输出一个整数，表示字符串 A 和 B 之间的编辑距离。

# 数据范围 1 ≤ |A|, |B| ≤ 1000 字符串只包含小写英文字母 # 样例解释 样例 1： 将 "kitten" 转换为 "sitting" 需要 3 次操作： kitten → sitten (将 'k' 替换为 's') sitten → sittin (将 'e' 替换为 'i') sittin → sitting (在末尾插入 'g') 样例 2： 将 "intention" 转换为 "execution" 需要 5 次操作。 # 提示 使用动态规划解决 定义 dp[i][j] 表示将 A 的前 i 个字符转换为 B 的前 j 个字符所需的最小操作次数 状态转移方程： 如果 A[i-1] == B[j-1]：dp[i][j] = dp[i-1][j-1] 否则：dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1 时间复杂度 O(n×m)，空间复杂度可以优化到 O(min(n,m)) # 扩展应用 编辑距离算法在以下领域有广泛应用： 拼写检查 DNA序列比对 自然语言处理 版本控制系统 抄袭检测