Day 56| 583. 两个字符串的删除操作 | 72. 编辑距离 |编辑距离总结篇

**Day56|583.两个字符串的删除操作 |72. 编辑距离**

在前面的文章中，我们讨论了如何计算两个字符串之间的编辑距离。今天，我们将继续讨论这个问题，并尝试用更高效的方法来解决它。

**什么是编辑距离？**

编辑距离（Edit Distance）是指两个字符串之间的最少编辑操作次数，例如插入、删除或替换一个字符。例如，如果我们有两个字符串 "kitten" 和 "sitting"，编辑距离为3，因为我们需要在 "kitten" 中添加 's'、'i' 和 'g'。

**动态规划**

我们可以使用动态规划来解决这个问题。动态规划是一种算法设计技术，它通过分解一个大问题成多个小子问题，来求解最优解。

在我们的例子中，我们定义一个2D 数组 `dp`，其中 `dp[i][j]` 表示第 i 个字符串的前缀和第 j 个字符串的前缀之间的编辑距离。

我们可以通过以下公式来计算 `dp[i][j]`：

* 如果第 i 个字符等于第 j 个字符，则 `dp[i][j] = dp[i-1][j-1]`
* 否则，`dp[i][j] =1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])`

**代码示例**

def edit_distance(s1, s2):
 m, n = len(s1), len(s2)
 dp = [[0] * (n +1) for _ in range(m +1)]

 # 初始化第一行和第一列 for i in range(m +1):
 dp[i][0] = i for j in range(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] =1 + min(dp[i -1][j], dp[i][j -1], dp[i -1][j -1])

 return dp[m][n]

# 测试s1 = "kitten"
s2 = "sitting"
print(edit_distance(s1, s2)) # Output:3