代码随想录算法学习心得 48 | 583.两个字符串的删除操作、72.编辑距离...
发布人:shili8
发布时间:2025-03-15 07:58
阅读次数:0
**代码随想录算法学习心得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]` 是否相等。如果相等,则答案与前一个子问题相同;否则,我们取两个子问题中最小值加一。
**总结**
在本篇文章中,我们讨论了两个相关的问题:两个字符串的删除操作和编辑距离。我们使用动态规划来解决这些问题,并提供了代码示例和注释。