代码随想录算法学习心得 48 | 583.两个字符串的删除操作、72.编辑距离...

**代码随想录算法学习心得48**

在前面的几篇文章中，我们讨论了关于动态规划的几个经典问题，如斐波那契数列、最长上升子序列等。在本篇文章中，我们将继续讨论两个相关的问题：两个字符串的删除操作和编辑距离。

**1.两个字符串的删除操作**

这个问题是这样的：给定两个字符串 `s1` 和 `s2`，我们需要计算出在不改变 `s1` 的前提下，如何删除 `s2` 中的字符，使得 `s1` 和 `s2` 最终变成相同。

**代码示例**

def deleteOperation(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])

 return dp[m][n]

# 测试s1 = "sea"
s2 = "eat"
print(deleteOperation(s1, s2)) # 输出:2

**注释**

* 我们使用了一个二维数组 `dp` 来存储每个子问题的答案。
* 初始化第一行和第一列时，我们直接将 `i` 和 `j` 的值赋给对应的元素，因为当 `s1` 或 `s2` 中的一个为空时，删除操作等于该字符串的长度。
* 填充 `dp` 表格时，我们检查 `s1[i -1]` 和 `s2[j -1]` 是否相等。如果相等，则答案与前一个子问题相同；否则，我们取两个子问题中最小值加一。

**2. 编辑距离**

这个问题是这样的：给定两个字符串 `s1` 和 `s2`，我们需要计算出在不改变 `s1` 的前提下，如何编辑 `s2`，使得 `s1` 和 `s2` 最终变成相同。

**代码示例**

def editDistance(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])

 return dp[m][n]

# 测试s1 = "kitten"
s2 = "sitting"
print(editDistance(s1, s2)) # 输出:3

**注释**

* 我们使用了一个二维数组 `dp` 来存储每个子问题的答案。
* 初始化第一行和第一列时，我们直接将 `i` 和 `j` 的值赋给对应的元素，因为当 `s1` 或 `s2` 中的一个为空时，编辑距离等于该字符串的长度。
* 填充 `dp` 表格时，我们检查 `s1[i -1]` 和 `s2[j -1]` 是否相等。如果相等，则答案与前一个子问题相同；否则，我们取两个子问题中最小值加一。

**总结**

在本篇文章中，我们讨论了两个相关的问题：两个字符串的删除操作和编辑距离。我们使用动态规划来解决这些问题，并提供了代码示例和注释。