当前位置:实例文章 » 其他实例» [文章]代码随想录算法学习心得 48 | 583.两个字符串的删除操作、72.编辑距离...

代码随想录算法学习心得 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]` 是否相等。如果相等,则答案与前一个子问题相同;否则,我们取两个子问题中最小值加一。

**总结**

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

相关标签:算法
其他信息

其他资源

Top