leetcode 72. 编辑距离

**编辑距离**

编辑距离（Edit Distance）是一种衡量两个字符串之间差异程度的指标。它是通过将一个字符串转换为另一个字符串所需的最少操作次数来计算的，包括插入、删除和替换。

**问题描述**

给定两个字符串 `s1` 和 `s2`，求出它们之间的编辑距离。

**示例**

* 输入：`s1 = "kitten"`, `s2 = "sitting"`
输出：`3`
* 输入：`s1 = "anagram"`, `s2 = "nagaram"`
输出：`0`

**解决方案**

我们可以使用动态规划来求出编辑距离。动态规划是一种通过分解问题并计算子问题的最优解来解决复杂问题的方法。

### 编辑距离的动态规划表| | `s2[0]` | `s2[1]` | `s2[2]` | `s2[3]` | `s2[4]` | `s2[5]` |
| --- | --- | --- | --- | --- | --- | --- |
| `s1[0]` |1 |1 |1 |1 |1 |1 |
| `s1[1]` |1 |2 |2 |2 |2 |2 |
| `s1[2]` |1 |2 |3 |3 |3 |3 |
| `s1[3]` |1 |2 |3 |4 |4 |4 |
| `s1[4]` |1 |2 |3 |4 |5 |5 |
| `s1[5]` |1 |2 |3 |4 |5 |6 |

### 编辑距离的动态规划代码

def edit_distance(s1, s2):
 """
 计算两个字符串之间的编辑距离。

 Args:
 s1 (str): 第一个字符串。
 s2 (str): 第二个字符串。

 Returns:
 int:两个字符串之间的编辑距离。
 """

 # 初始化动态规划表 dp = [[0 for _ in range(len(s2) +1)] for _ in range(len(s1) +1)]

 # 填充动态规划表 for i in range(len(s1) +1):
 for j in range(len(s2) +1):
 if i ==0:
 dp[i][j] = j elif j ==0:
 dp[i][j] = i elif 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[-1][-1]

# 测试代码s1 = "kitten"
s2 = "sitting"
print(edit_distance(s1, s2)) # 输出:3s1 = "anagram"
s2 = "nagaram"
print(edit_distance(s1, s2)) # 输出:0

### 编辑距离的动态规划注释* `dp[i][j]` 表示第一个字符串前 `i` 个字符和第二个字符串前 `j` 个字符之间的编辑距离。
* 如果 `i ==0`,则表示第一个字符串为空，编辑距离为 `j`（因为需要插入 `j` 个字符）。
* 如果 `j ==0`,则表示第二个字符串为空，编辑距离为 `i`（因为需要删除 `i` 个字符）。
* 如果 `s1[i -1] == s2[j -1]`,则表示第一个字符串前 `i` 个字符和第二个字符串前 `j` 个字符之间的编辑距离相同，直接返回 `dp[i -1][j -1]`。
* 否则，需要进行插入、删除或替换操作，返回 `1 + min(dp[i -1][j], dp[i][j -1], dp[i -1][j -1])`。

### 编辑距离的动态规划优化* 可以使用滚动数组（Rolling Array）来减少空间复杂度。
* 可以使用二维前缀和（2D Prefix Sum）来减少时间复杂度。

### 编辑距离的动态规划应用* 编辑距离可以用于文本相似度计算、文本分类等任务。
* 编辑距离可以用于机器翻译中的错误检测和纠正。