Day56 583. 两个字符串的删除操作 72. 编辑距离

**Day56:583.两个字符串的删除操作**

在本题中，我们需要实现一个函数，来计算出两个给定字符串之间的最小编辑距离。这个问题可以转化为动态规划的问题。

### 编辑距离定义：

编辑距离是指将一个字符串转换成另一个字符串所需的最少操作次数。这些操作包括插入、删除和替换一个字符。

### 动态规划解决方案：

我们可以使用一个二维数组来存储两个字符串之间的编辑距离。这个数组的行数等于第一个字符串的长度，列数等于第二个字符串的长度。

def minDistance(word1, word2):
 m, n = len(word1), len(word2)
 # 初始化动态规划数组 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):
 cost =0 if word1[i -1] == word2[j -1] else1 dp[i][j] = min(dp[i -1][j] +1, # 删除 dp[i][j -1] +1, # 插入 dp[i -1][j -1] + cost) # 替换 return dp[m][n]

### 编辑距离示例：

print(minDistance("horse", "ros")) # 输出:3print(minDistance("intention", "execution")) # 输出:5

在上面的示例中，我们可以看到编辑距离的计算结果。

### 编辑距离总结：

本题使用动态规划解决方案来计算两个字符串之间的最小编辑距离。这个问题可以转化为一个二维数组的问题，通过填充这个数组，我们可以得到最终答案。

**Day56:72. 编辑距离**

在本题中，我们需要实现一个函数，来计算出两个给定字符串之间的最小编辑距离。这个问题可以转化为动态规划的问题。

### 编辑距离定义：

编辑距离是指将一个字符串转换成另一个字符串所需的最少操作次数。这些操作包括插入、删除和替换一个字符。

### 动态规划解决方案：

我们可以使用一个二维数组来存储两个字符串之间的编辑距离。这个数组的行数等于第一个字符串的长度，列数等于第二个字符串的长度。

def editDistance(word1, word2):
 m, n = len(word1), len(word2)
 # 初始化动态规划数组 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):
 cost =0 if word1[i -1] == word2[j -1] else1 dp[i][j] = min(dp[i -1][j] +1, # 删除 dp[i][j -1] +1, # 插入 dp[i -1][j -1] + cost) # 替换 return dp[m][n]

### 编辑距离示例：

print(editDistance("horse", "ros")) # 输出:3print(editDistance("intention", "execution")) # 输出:5

在上面的示例中，我们可以看到编辑距离的计算结果。

### 编辑距离总结：

本题使用动态规划解决方案来计算两个字符串之间的最小编辑距离。这个问题可以转化为一个二维数组的问题，通过填充这个数组，我们可以得到最终答案。