代码随想录算法训练营第五十六天|583. 两个字符串的删除操作、72. 编辑距离、动态规划之编辑距离总结篇

**代码随想录算法训练营第五十六天**

##583.两个字符串的删除操作### 题目描述给定两个字符串 `s1` 和 `s2`,以及一个整数 `n`,要求你找到从 `s1` 到 `s2` 的最短编辑距离。编辑距离是指将 `s1` 编辑成 `s2` 所需的最少操作次数。

### 解决方案我们可以使用动态规划来解决这个问题。首先，我们定义一个二维数组 `dp`，其中 `dp[i][j]` 表示从 `s1[0..i-1]` 到 `s2[0..j-1]` 的最短编辑距离。

def minDistance(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 # 填充动态规划数组 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(minDistance(s1, s2)) # 输出:3

##72. 编辑距离### 题目描述给定两个字符串 `s1` 和 `s2`,要求你找到从 `s1` 到 `s2` 的最短编辑距离。

### 解决方案我们可以使用动态规划来解决这个问题。首先，我们定义一个二维数组 `dp`，其中 `dp[i][j]` 表示从 `s1[0..i-1]` 到 `s2[0..j-1]` 的最短编辑距离。

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 # 填充动态规划数组 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(editDistance(s1, s2)) # 输出:3

## 动态规划之编辑距离总结篇### 总结本文介绍了两个字符串的删除操作和编辑距离问题的解决方案。我们使用动态规划来求出从一个字符串到另一个字符串的最短编辑距离。

### 动态规划数组我们定义一个二维数组 `dp`，其中 `dp[i][j]` 表示从 `s1[0..i-1]` 到 `s2[0..j-1]` 的最短编辑距离。

# 初始化动态规划数组dp = [[0] * (n +1) for _ in range(m +1)]

### 填充第一行和第一列我们填充第一行和第一列的值，分别表示从 `s1` 到空字符串和从空字符串到 `s2` 的最短编辑距离。

# 填充第一行和第一列for i in range(m +1):
 dp[i][0] = ifor j in range(n +1):
 dp[0][j] = j

### 填充动态规划数组我们填充动态规划数组的值，根据两个字符串的相似度来决定。

# 填充动态规划数组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])

### 最终结果我们返回动态规划数组的最后一个值，表示从 `s1` 到 `s2` 的最短编辑距离。

return dp[m][n]

### 测试用例我们测试这个函数使用两个字符串 `"kitten"` 和 `"sitting"`,并输出结果为3。

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

### 总结本文介绍了两个字符串的删除操作和编辑距离问题的解决方案。我们使用动态规划来求出从一个字符串到另一个字符串的最短编辑距离。